By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.
5
9 6
4 6 8
0 7 1 5
i.e. 5 + 9 + 6 + 7 = 27.
Write a program in Java to find the maximum total from top to bottom in the included file ‘triangle.txt’ - a text file containing a triangle with 100 rows.
git clone https://github.com/fletcher86/triangle-max-sum.git cd triangle-max-sum ./gradlew clean build java -jar ./build/libs/triangle-max-sum-1.0.jar < triangle.txt
The computed triangle sums were computed from a bottom up approach because if using a top down approach the sum may not be maximized. For example, using a top down approach, it is possible to have sums weighted toward one side of the triangle, but a single outlier on the opposite side and bottom of the triangle that could have impacted the max sum calculation and would have been missed with a top down approach. In order to take into account this possibility, a bottom up approach was necessary.
Sums were rolled up from the bottom up as follows.
5
9 6
4 6 8
0 7 1 5
5
9 6
11 13 12
5
22 19
27
The computed output for "triangle.txt" is
Max Sum = 732506
The computed output for "triangle0.txt" is
Max Sum = 23
The computed output for "triangle1.txt" is
Max Sum = 1074
The computed output for "triangle2.txt" is
Max Sum = 27
This last input file, triangle2.txt, is the same input described in the problem description above.