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)

Correct-bearophile (talk)

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 53^rd 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). -- Gerard Schildberger (talk) 06:23, 4 March 2014 (UTC)

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 used to generate the above monotonous (above) triangles and find the maximum triangle path sum is: <lang rexx>/*REXX program finds the max sum of a "column" of numbers in a triangle.*/ numeric digits 10 /*increase this for big triangles*/ parse arg L . /*get number of lines in triangle*/ if L== then L=1000 /*Not given? Then use the default*/

1. .=0

     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.c=q                      /*build a triangle line number.  */
         end   /*c*/                  /*each line is:  1 2 3 4 5 6 ··· */
     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    /*replace the previous #. */
         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:    4501500  for  3000  rows.
The maximum path sum:    8002000  for  4000  rows.
The maximum path sum:   50005000  for  10000  rows.

The last entry was obtained via a specialized version of the (above) REXX program   (due to a constraint on virtual memory). -- Gerard Schildberger (talk) 06:23, 4 March 2014 (UTC)

---