Maximum path sum in a triangle

Problem Statement

Finding the maximum path sum in a triangle is a very common programming problem. You are given a triangle of numbers which can be represented as below. You are allowed to start from the top of the triangle and move to either of the two number below it. As we move down from the top to the bottom in multiple ways, we keep adding the numbers for each node we visit. The goal is to maximize the sum . A more formal problem statement can be found on the Project Euler website.

How to approach the problem

At any point you have two choices you can go to the number below the current number or to the adjacent number. An example could be below:

The possible choices we have for the above sample is :

  • 3, 7, 2, 8
  • 3, 7, 2, 5
  • 3, 7, 4, 5
  • 3, 7, 4, 9
  • 3, 4, 4, 5
  • 3, 4, 4, 9
  • 3, 4, 6, 9
  • 3, 4, 6, 3

Out of the above 8 choices, we calculate that the sum for path 3, 7, 4, 9 is 23 and it is the maximum of all other sums possible.

  • The idea is to generate all possible paths from the top to the bottom.
  • At every point we have 2 directions to search and we explore every possible path through recursion.
  • After getting the result at every point we compare the path results and return on the corresponding data based on the fact which ever is maximum.

Code Sample for maximum path sum in a triangle

Here is the recursive code which we derived based on the above discussion.

Storing the input

We store the input in a two dimensional array and the apex of the triangle is stored at (0,0). It might look like a right triangle the way it is stored.

And finally the getSum method is invoked with the arguments (0,0,0). This means, we start with level 0, and the element in the matrix is at row 0 and column 0.

Analysis

As we are solving this through recursion and at each level the recursion tree divides itself into two problem of smaller size and does some constant work. The size of the problem is reduced by 1 at each recursive step. So we can write the running time as

T(N) = 2T(N-1) + O(1)  where N is the depth of the triangle.

This will result into a O(2^N) running time.

The space required is almost constant as we are not using extra space, hence we can write it O(1)

The code below explains implementation in java:

Summary

Above we discussed a recursive solution which is definitely doing a lot of rework, adding memoization to this solution would help. It will further help if we can use dynamic programming and get rid of the recursion at the cost of some extra space. In the next post , we will explore the other two solutions.