Maximum triangle path sum: Difference between revisions

Content added Content deleted

Inline

@@ Line 312: / Line 312: @@
     };
-    int last = sizeof( triangle ) / sizeof( int ),
+    const int size = sizeof( triangle ) / sizeof( int );
+    const int tn = static_cast<int>(sqrt(2.0 * size));
-	tn = 1;
-    while( ( tn * ( tn + 1 ) / 2 ) < last ) tn += 1;
+    assert(tn * (tn + 1) == 2 * size);    // size should be a triangular number
+    // walk backward by rows, replacing each element with max attainable therefrom
+    for (int n = tn - 1; n > 0; --n)   // n is size of row, note we do not process last row
+        for (int k = (n * (n-1)) / 2; k < (n * (n+2)) / 2; ++k)
+            triangle[k] += std::max(triangle[k + n], triangle[k + n + 1]);
-    last--;
-    for( int n = tn; n >= 2; n-- )
-    {
-	for( int i = 2; i <= n;  i++ )
-	{
-	    triangle[last - n] = triangle[last - n] + std::max( triangle[last - 1], triangle[last] );
-	    last--;
-	}
-	last--;
-    }
     std::cout << "Maximum total: " << triangle[0] << "\n\n";
-    return system( "pause" );
 }
 </lang>