Skip to main content

Maximum Path Sum

Problem Statement : Starting from top to bottom and moving to adjacent numbers below, find the maximum total for triangle.
problem

By looking it at the given triangle for few minutes you would see that below is the path having maximum sum i.e. 23.
answer

First approach that may pop in one's mind to solve this problem would be a brute force algorithm. This would be trying every route to find the max sum. The actual number of iterations that will take place for this approach would be 2n, which would be a problem if size of triangle increases.
Bottom to Top Approach
This approach is looking the triangle from bottom to top. First visualize the triangle as follows:
step0
We transform the triangle in sort of tree structure and then only 2 steps need to be repeated until we reach the root node.
Step 1: Choose the max leaf node from the two child leaf nodes.
Step 2: Add the chosen leaf node to the parent node.
Repeat this until you get to root node. For this triangle this is how it goes, chose the max leaf nodes among the pairs.
step1

Add the chosen nodes to parent.
step2

These steps are repeated until we get to root node.
step3
which gives us 23 the answer.

Comments

Popular posts from this blog

Guide : Spring Boot with Apache CXF for REST services

In this series of guide, we are going to explore writing REST services with Apache CXF using Spring Boot. The project is build using maven. I assume that you already know how to use maven. Step 1 : Adding dependencies for Spring Boot By default you have to inherit the parent pom of spring boot, but that cannot be followed everytime, so I use an alternative to that. I basically add spring boot pom as dependency so that it brings all the dependencies. <properties> <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding> <java.version>1.8</java.version> <spring.version>1.4.3.RELEASE</spring.version> <cxf.version>3.1.10</cxf.version> </properties> <dependencies> <dependency> <!-- Alternative to inheriting from parent spring pom --> <groupId>org.springframework.boot</groupI…

Enabling CXF goodies in Spring Boot

In this post we are going to add some of the CXF features to our existing app that we developed in previous post. These features are : ID LoggingJackson Provider for POJO to JSON conversionSwagger 2 documentationStep 1: Configuration class Create a RestServer class in config package as shown below
package org.blog.config;importcom.fasterxml.jackson.jaxrs.json.JacksonJsonProvider;importorg.apache.cxf.feature.LoggingFeature;importorg.apache.cxf.jaxrs.swagger.Swagger2Feature;importorg.springframework.context.annotation.Bean;importorg.springframework.context.annotation.Configuration;/** * Created by Anand_Rajneesh on 3/23/2017. */@ConfigurationpublicclassRestServer{@Beanpublic JacksonJsonProvider jsonProvider(){returnnewJacksonJsonProvider();}@Beanpublic LoggingFeature loggingFeature(){returnnewLoggingFeature();}@Beanpublic Swagger2Feature swagger(){ Swagger2Feature swagger =new Swagger2Feature(); swagger.setBasePath("/services"); swagger.setContact("…

PL SQL Cheatsheet

PL/SQL Syntax for reference

Basic PL/SQL block
DECLARE --variable declarations go here BEGIN --program logic goes here END;
Functions - Named pl/sql blocks mainly used for computation and not for write operations. They return value to the caller as defined in function.
CREATE OR REPLACE FUNCTION myFunc( arg1_in IN VARCHAR2, arg2_in VARCHAR2) RETURN BOOLEAN AS RETURN true; END;
Procedure - Named pl/sql block used for write operations.
CREATE OR REPLACE PROCEDURE myProc( arg1_in IN VARCHAR2, arg2_in IN VARCHAR2) AS arg3 VARCHAR2(2048); arg4 BOOLEAN; BEGIN --logic END;
Variable Declarations 
arg VARCHAR2(2048) := 'myString'; arg BOOLEAN := true; arg NUMBER := 10;
IF ELSE Conditions
IF (condition) THEN --logic 1 ELSIF (condition2) THEN --logic 2 ELSE --logic3 END IF;
SWITCH Statements
With selector
arg1 NUMBER := 0; CASE arg1 WHEN 0 THEN --logic; WHEN 1 THEN --…