Pyramid Problem

[aakashjohari]

Suppose there is a pyramid like
5
4 3
2 3 1
8 3 2 2
7 8 9 1 2

I want to find the path in this pyramid so that the sum of the numbers in that path is maximum. I can move to next row either left or right. as i am at 5 then i can move to 4 or 3. if am at 4 then i can move to 2 or 3. Answer should be the maximum sum only.

i will appreciate a good advice.

[jsmith]

If there are no restrictions on the values each node can have, then you'll essentially need to traverse every possible path and calculate the sum of each path.

[aakashjohari]

But how to get this sum it is the main problem...
please give any algorithm or solution so that i can understand

[Faldrax]

1) Create a jagged array of int for the pyramid and populate with the values.
2) Create an array to hold the indicies in the rows which result in the highest total.
3) Loop round the first array array top to bottom and cacluate the total.
4) Set this total = highest total, set array og highest indicies = indices used.
5) Repeat loop down jagged array with 1 index different on 1 of the sub-arrays.
6) If total > highest, assign to highest and reset indicies store.
7) repeat for every combination.

[jsmith]

Another way is to create a binary tree with each node holding one of the values and then perform a depth first "search" across the entire tree.