1

I'm trying to find an algorithm in which i can go through a numerical pyramid, starting for the top of the pyramid and go forward through adjacent numbers in the next row and each number has to be added to a final sum. The thing is, i have to find the route that returns the highest result.

I already tried to go throught the higher adjacent number in next row, but that is not the answer, because it not always get the best route.

I.E.

        34
      43  42
    67  89  68
  05  51  32  78
72  25  32  49  40

If i go through highest adjacent number, it is:

34 + 43 + 89 + 51 + 32 = 249

But if i go:

34 + 42 + 68 + 78 + 49 = 269

In the second case the result is higher, but i made that route by hand and i can't think in an algorithm that get the highest result in all cases.

Can anyone give me a hand?

(Please tell me if I did not express myself well)

Improve this question
7
  • 1
    This question appears to be off-topic because it is about Math. Commented Feb 3, 2014 at 3:08
  • 1
    @MitchWheat How is it about math? It's about an algorithm, is it not? Commented Feb 3, 2014 at 3:10
  • 1
    And as Turing proved, all algorithms are math. I guess we should merge to the sites. Commented Feb 3, 2014 at 3:14
  • 1
    Let's not get unnecessarily pedantic; the point is this question is not off topic. Commented Feb 3, 2014 at 3:15
  • 1
    Do a search for longest path in a weighted directed acyclic graph. Commented Feb 3, 2014 at 3:17

2 Answers 2

Reset to default
6

Start with the bottom row. As you go from left to right, consider the two adjacent numbers. Now go up one row and compare the sum of the number that is above the two numbers, in the row above, with each of the numbers below. Select the larger sum.

Basically you are looking at the triangles formed by the bottom row and the row above. So for your original triangle, 

        34
      43  42
    67  89  68
  05  51  32  78
72  25  32  49  40

the bottom left triangle looks like,

  05
72  25

So you would add 72 + 05 = 77, as that is the largest sum between 72 + 05 and 25 + 05.

Similarly,

  51
25  32

will give you 51 + 32 = 83.

If you continue this approach for each two adjacent numbers and the number above, you can discard the bottom row and replace the row above with the computed sums.

So in this case, the second to last row becomes

77  83  81  127

and your new pyramid is

      34
    43  42
  67  89  68
77  83  81  127

Keep doing this and your pyramid starts shrinking until you have one number which is the number you are after.

    34
  43  42
150 172 195

   34
215  237

Finally, you are left with one number, 271.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Hey thanks! It works, i could code it and it works perfect. Has this algorithm a name?
2

Starting at the bottom (row by row), add the highest value of both the values under each element to that element.

So, for your tree, 05 for example, will get replaced by max(72, 25) + 05 = 77. Later you'll add the maximum of that value and the new value for the 51 element to 67.

The top-most node will be the maximum sum.

Not to spoil all your fun, I'll leave the implementation to you, or the details of getting the actual path, if required.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.