Triangle Puzzle
Consider the triangle below. This triangle would be represented by the following input file.
5 9 6 4 6 8 0 7 1 5
By starting at the top and moving to adjacent numbers on the row below, one creates a path to the bottom of the triangle. There are many such paths in a triangle, which may have different weights. The weight of a path is the sum of all numbers encountered along the way. Write a program to find the weight of the path with the highest weight for a given triangle.
In above example, the maximum sum from top to bottom is 27, and is found by following the bold text above path. 5 + 9 + 6 + 7 = 27.
(More formally: The triangle is an acyclic digraph, and each number represents the value of a node. Each node has either two or zero direct successors, as shown by the arrows above. A complete path is a path which begins at the root node—the one with no immediate predecessors—and ends at a node with no immediate successors. The weight of a complete path is the sum of the values of all nodes in the path graph. Write a program which finds the weight of the complete path with the largest weight for a given triangle.)
Bigger test sample data :
9235 9096 637 973 3269 7039 3399 3350 4788 7546 1739 8032 9427 976 2476 703 9642 4232 1890 704 6463 9601 1921 5655 1119 3115 5920 1808 645 3674 246 2023 4440 9607 4112 3215 660 6345 323 1664 2331 7452 3794 7679 3102 1383 3058 755 1677 8032 2408 2592 2138 2373 8718 8117 4602 7324 7545 4014 6970 4342 7682 150 3856 8177 1966 1782 3248 1745 4864 9443 4900 8115 4120 9015 7040 9258 4572 6637 9558 5366 7156 1848 2524 4337 5049 7608 8639 8301 1939 7714 6996 2968 4473 541 3388 5992 2092 2973 9367 2573 2658 9965 8168 67 1546 3243 752 8497 5215 7319 9245 574 7634 2223 8296 3044 9445 120 7064 1045 5210 7347 5870 8487 3701 4301 1899 441 9828 3076 7769 8008 4496 6796