Problem 18

For this problem, we are asked to find the maximum sum path through a triangle. While this problem can be solved by brute force, its sister problem #67 cannot be. Because of this, it is a good idea to go ahead and solve this problem in a more optimized way. To do this, we can first store the triangle in a vector formed of vectors, which mimics the levels found in the triangle. Then, rather than starting at the top of the triangle, we can start at the bottom and find the greatest sum set at the lowest level. Once we find the maximum, we add it to the running sum and move to the next set. Finally, once that level is completed, we move up the triangle by one row and continue the process. After completing this, we get our final answer of 1074.