## Maximum Sum Path in a Triangle

*Problem Statement:* You have been given a triangle of numbers (as shown). You are supposed to start at the apex (top) and go to the base of the triangle by taking a path which gives the maximum sum. You have to print this maximum sum at the end. A path is formed by moving down 1 row at each step (to either of the immediately diagonal elements)

The first method that comes to everyone’s mind is **brute-force**. But in a second or two, you would discard the idea knowing the huge time complexity involved in traversing each possible path and calculating the sum. What we need is a smarter approach.

I hope you remember about the *optimal substructure *I talked about earlier relating to Dynamic Programming. Can you see one such optimal substructure here? You can *build* a solution as you drop down each row. You can calculate the best path till the particular node in the triangle as you move down and finally you’ll have your maximum sum in the last row somewhere. Here is the algorithm :

Take another similar array (or your preferred data structure), let us say MAX_SUM[][]

For each ELEMENT in particular ROW and COLUMN

{

If ( ELEMENT is FIRST ELEMENT of ROW)

{

MAX_SUM[ROW][COLUMN] = ELEMENT + FIRST element of (ROW-1)

}

Else If (ELEMENT is LAST ELEMENT of ROW)

{

MAX_SUM[ROW][COLUMN] = ELEMENT + LAST element of (ROW-1)

}

Else

{

MAX_SUM[ROW][COLUMN] = ELEMENT + maximum( element at [ROW-1][COLUMN-1], element at [ROW-1][COLUMN])

//recursive formula calculating max_sum at each point from all possible paths till that point

}

}

Once you have this array, you just need to find the maximum value in the last row of this new array and that will be your maximum sum! 🙂

For the example I took, the array MAX_SUM would look like, (and my answer would be 23)

What I am doing is for each element, checking the maximum of the possible paths to this node and adding the current elements value to it. If you still don’t understand, leave a comment and I’ll explain each and every step in excruciating detail. 😛

**TASK FOR YOU:*** Find the elements of this path.*

This can be looked at as a tree problem.

If you just re-adjust and make the triangle into a tree,

3

7 4

2 4 6

8 5 9 3

it’ll look like this

3

/ \

7 4

/ \ / \

2 4 4 6

/ \ / \ / \ / \

8 5 5 9 5 9 9 3

Now it’s basically a matter of finding the max-sum-path…

Why do you want to complicate the question by introducing the “tree” data structure when it can be easily solved in place as an array. This dynamic programming solution solves it in one traversal of the array. Even thinking about tree makes the solution you will end up with much more complicated than it actually is.

I’m not challenging your method, so don’t look at it as complicating the problem.. its just another approach 🙂

Cool. 🙂

Would this prog be going upwards or downwards?

My method is a slight variation, but it was kind of stemming off your idea:

Array[A][B]+=Great_of(Array[A+1][B],Array[A+1][B+1];

so basically, every value is replaced with sum with the greater value of two values that it can reach.

So

3

7 4

2 4 6

8 5 9 3 Turn into

3

7 4

10 13 15 (since 2+8 is better than 2+5 and etc)

3

20 19

and 23 in the end.

Haha. You are just going the other way round 🙂 Up or down – that’s a question for philosophers. We would be fine doing it both ways.

Another approach : Build a graph , add 2 node sink & source to bottom and top rows . Get topological order , based on this order relax the edges (taking max among the possibilities). Ideally its a longest path pblm in weighted acyclic digraph. .Can be solved in O(E+V)

Hmm. How is that any better, though? First, you are using extra space. And second, the time complexity doesn’t improve.