Home > Applied Algorithms, Arrays, Dynamic Programming > Maximum Sum Path in a Triangle

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.

Advertisements
  1. Anup
    October 29, 2011 at 1:03 pm

    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…

    • October 29, 2011 at 3:40 pm

      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.

  2. Anup
    October 30, 2011 at 7:29 am

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

  3. Shawn
    May 5, 2013 at 5:57 am

    Would this prog be going upwards or downwards?

  4. JMan_Zx
    October 22, 2013 at 10:25 pm

    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.

    • December 5, 2014 at 10:54 am

      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.

  5. August 6, 2014 at 10:49 am

    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)

    • December 5, 2014 at 10:45 am

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

  1. No trackbacks yet.

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

%d bloggers like this: