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:

step0We 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.

step1Add the chosen nodes to parent.

step2These steps are repeated until we get to root node.

step3which gives us 23 the answer.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s