CODEWITHSUNDEEP
algorithmmath
Vertig0
Vertig0

Reputation: 623

Pyramidal algorithm

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)

Upvotes: 1

Views: 507

Answers (2)

Mars
Mars

Reputation: 4995

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.

Upvotes: 6

Bernhard Barker
Bernhard Barker

Reputation: 55589

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.

Upvotes: 2

Related Questions