16th May
2010
written by admin

Given a triangle filled with values find the maximum sum that can be achieved by traversing from top to bottom.

Sum Of A Triange

I spent a bit of time thinking about the best way to accomplish this since on Project Euler one of the triangles is 100 lines in the text file.  I thought about an algorithm that basically traverses the largest branch in the tree, but that doesn’t always yield the maximum sum.  So then I realized that I don’t really need to know the actual values of the triangle, only the sum of up to that point.  So I basically came up with a way that calculates the maximum value at a point in the triangle by starting from the top and working my way down.  So for example A triangle like this:

8

5   43

41  36  12

Would generate a summed tree that looks like this

8

13   51

54  79 55

So then all I need to do is iterate through the final row of values to find the maximum sum.  I’d be interested of hearing better solutions to this problem if anyone has them.  My implementation uses a very simple parsing method to pull the numbers from a text file, along with an array of std::vector’s to build the tree.  I chose vectors over building a binary tree mainly for the indexing capability.

I have an entire project file full of Project Euler solutions which is why you’ll see names like SolveEuler18, I post-fix everything with 18 just to make it easier to pick out in my Visual Studio project.