Given a triangle of numbers as below, devise an algorithm to determine the maximum sum traveling from the top of the triangle to the base made by moving from one row to the next by adjacent cells.
5 6 3 2 8 6 9 5 4 7In this example the route of maximum sum (24) from top to bottom is: 5 -> 6 -> 8 -> 5. Make sure your algorithm is scalable to larger triangles.
Brute force approach will obviously not scale. Think of how you can go row-by-row attaining the max.
5 6 3 2 8 6 9 5 4 7For each digit in the triangle (other than the final row), there are only two routes for progressing to the next row. For the example in the triangle above, digit 2 in the second to last row can only progress to either 9 or 5. Calculating the maximum possible sum for each row going bottom to top, we can extract an algorithm that is highly efficient. We start with the second to last row and calculate the maximum sum attainable for each digit.
5 6 3 11 13 13
We progress with this method sequentially up until the top row.
5 19 16
Finally, the maximum sum will end in the apex of the triangle:
This method is highly scalable and much more efficient than a brute force approach in calculating all possible route. As for actually coding the solution,
Thoughts or alternate solution? Let us know in the comments below!
Thanks to Bill for a correction on this answer!