Prob 0018 ‐ Maximum Path Sum I - maccergit/Euler GitHub Wiki

Once a good approach to this is done, we can also try Prob 0067.

01

One approach is to try and find all paths through the tree - but we already know that will be slow (the problem tells us that it does not scale), and implementing it appears to be a bit of trouble. However, if we realize that the problem can be broken into pieces, we can try a recursive approach. Note that from the root of the tree, there are only two paths that can be taken - each forming a sub-tree of the original tree, and the final result will be the larger of the largest path from each sub-tree plus the value for the root. However, finding the largest path from a sub-tree is the same as the original problem, just with a smaller tree (the sub-tree). The exit condition for the recursion is the trivial case of getting a tree that is just a single element - it's the value of the that element. Note that memoization is probably not much gain here, as we are unlikely to get the same tree multiple times.

As the problem states, this is a small enough data set that we can solve this using brute force - but if we run this repeatedly using larger and larger subsets of the problem data, we can see that the execution time will rapidly grow beyond any reasonable value. Since the number of paths doubles with each increase, it looks like we are looking at $\mathcal{O}({2^{limit}})$ execution time :

02

SPOILER ALERT - The "trick" algorithm is revealed here.

On observation, we note that as we traverse every path, we end up hitting all of the last nodes in the tree. If we start with the last nodes, we observe that every leaf node in the sub-tree above the last row covers all the possible paths, except for the choice of two nodes in the last row. Thus, looking at the last row of the sub-tree means we get all the possible paths without their last node - and the largest path will be the largest of those paths plus the larger of the two possible nodes it could take. Since we don't know in advance which of the paths in the sub-tree will be largest, we can simply examine the choices for each of the leaf nodes in the sub-tree and pick the larger path. Since we are using a running total, and the sum is the same if we add the items in order or in reverse order, we can add the value to the sub-tree leaf nodes, and then iterate again on the sub-tree. Once we get to the root, it will contain the total for the longest path. This should scale with the number of elements in the tree - which is much better than before :

NOTE: I talk about "iterating" when describing the solution - but I implemented it using recursion. Since we are using tail recursion, it should correspond roughly to iteration - but it's easier to implement. The downside is there is a small danger of running out of stack space, something that would not be an issue in an iterative approach.