Talk:Maximum triangle path sum
numbers in the triangle
Just a curiosity, where those numbers in the given triangle chosen at random? -- Gerard Schildberger (talk) 09:02, 25 February 2014 (UTC)
efficiency of the REXX solution
To find the efficiency of the REXX solution, a system of defining the lines (rows) of the triangle was chosen such that each row could be easily be generated, and more importantly, have a verifiable answer (for some largish even number of rows).
The algorithm used was to start each row (the left end) with unity, and increase each column number by one, so that the 53rd number on row 53 (and every other higher row) is 53. Verifications of the maximum triangle path sum (for some triangles) can be easily seen by the results (below).
A triangle of nine rows looks like:
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9
The REXX program is: <lang rexx>/*REXX program finds the max sum of a "column" of numbers in a triangle.*/ parse arg L . /*get number of lines in triangle*/ if L== then L=100 /*Not given? Then use the default*/ @.=
do r=1 for L; q=0 /*construct lines of the triangle*/ do c=1 for r; q=q+1 /*leftmost number is always unity*/ @.r=@.r q /*append number to triangle line.*/ end /*c*/ /*each line is: 1 2 3 4 5 6 ··· */ end /*r*/
- .=0
do r=1 while @.r\== /*build a version of the triangle*/ do k=1 for words(@.r) /*build a row, number by number. */ #.r.k=word(@.r,k) /*assign a number to an array num*/ end /*k*/ end /*r*/
do r=L by -1 to 2; p=r-1 /*traipse through triangle rows. */ do k=1 for p; kn=k+1 /*re-calculate the previous row. */ #.p.k=max(#.r.k,#.r.kn)+#.p.k /*maybe replace the prev #.*/ end /*k*/ end /*r*/
say 'The maximum path sum:' right(#.1.1,digits()), /*display top row # */
" for " L ' rows.' /* and the # of rows.*/ /*stick a fork in it, we're done.*/</lang>
output for various runs are (multiple runs have their output consolidated):
The maximum path sum: 5050 for 100 rows. The maximum path sum: 20100 for 200 rows. The maximum path sum: 45150 for 300 rows. The maximum path sum: 80200 for 400 rows. The maximum path sum: 125250 for 500 rows. The maximum path sum: 180300 for 600 rows. The maximum path sum: 245350 for 700 rows. The maximum path sum: 320400 for 800 rows. The maximum path sum: 405450 for 900 rows. The maximum path sum: 500500 for 1000 rows. The maximum path sum: 2001000 for 2000 rows. The maximum path sum: 8002000 for 4000 rows. The maximum path sum: 50005000 for 10000 rows.