# Project Euler – Maximum path sum (Part 2)

Time to pick up a Project Euler problem that was resting on my mental shelf since the beginning of September, “Maximum Path Sum I”. For a quick introduction just jump to the old post.

# What about using a tree?

Using a tree and traversing it, most likely recursively, was my first idea.

As one can possibly guess, many possible tree implementations exist.
Here is an example taken from Stanford’s computer science department:

Using such a construct, I started building a tree “by hand”. Something along the lines of…

root = new Node(75);
root.left = new Node(95);
root.left = new Node(64);
root.left.left = new Node(17);
...

Definitely not the way to go. Gave up. Failed.

# Pen and paper approaches

I had already figured out that the number I was looking for must be somewhere between 1064 and 1313.
1064: Start at the top and always pick the highest adjacent number.
1313: Just take the highest number of each row and add them all together, even though no connection exists, just to get a very rough estimate.

Then I started browsing the interwebs for “inspiration”, which gave me some ideas, but unfortunately the solution as well.

The amount of new knowledge gained so far: ZERO! But at least I now had access to the Project Euler forum posts for this particular problem. The holy grail of algorithmic knowledge.

Apparently some forum members figured this one out using just “pen and paper”:

I just make a greedy approach with eyes, done in the second try.

Or:

I did this by eye – buffed the triangle with spaces properly and replaced everything under 50 with ’00’ in a text editor, then chose the line that looked the most line-ish 🙂 solved in about 3 minutes.

These were unfortunately not the answers to satisfy my curiosity, but I also found forum posts which looked way more algorithmic:

just paper and pencil, reduce the bottom two lines to one line containing the best sum for each element, then proceed the same with the upper level and so on. at the top you will have the answer. Same algorith will be used at the triangle with 1000 lines. (hope will work) best regards

Someone named “mather” was the first one to post an answer along these lines.

Let’s have a look at his approach using the sample triangle given in the original problem description:

The algorithm starts at the bottom line, not on the top. I stick to the tree language by the way. Each leaf has a parent node. For example 2 is the parent node of leaf 8 and 5. 4 is the parent node of leaf 5 and 9 and so on.

Now, for each node (leaf) we create a the sum of its value and the value of its parent. The higher sum will be kept. We just store it as new value in the parent node.

8 + 2 = 10.
5 + 2 = 7.
10 > 7, keep 10.

Now 5 + 4 = 9.
9 + 4 = 13.
13 > 9, keep 13.

And last 9 + 6 = 15.
3 + 6 = 9.
15 > 9, keep 15.

That’s how to proceed upwards.

The final result is 23, which is exactly the number we are looking for.

And this is an algorithm that can be turned into  a program! Almost there.

# Finally a program

Credit goes to a user named “dchuhay”.

This little program follows exactly the approach described above.

The program flow starts in this row of the pyramid:

For each node value in this row the algorithm builds two sums, one for each of the two child-nodes, and stores the higher sum in the original node.

E.g. i = 13, j =0. The node triangle[13][0] is 63.
Now, is triangle[13 + 1][0] < triangle[13 + 1][0 + 1]? 04 < 62? Yes!
Therefore add triangle[13 + 1][0 + 1] to triangle[13][0] and store it as new value in triangle[13][0]. 63 + 62 = 125.

Now proceed with the next node in this row, which is 66, until we run out of values.
Once all values in this row were replaced by new values (= highest sum) proceed on, one row upwards.

for (int i = triangle.length – 2; i >= 0; i–) is correct, as we need to assign a value to triangle[0][0], which will be our final result.

# Dynamic programning

One forum post containing a C# solution starts with the following line: