Maximum sum of a path in a Right Number Triangle | C ++ program to print maximum sum in a right triangle of numbers ; function to find maximum sum path ; Adding the element of row 1 to both the elements of row 2 to reduce a step from the loop ; Traverse remaining rows ; Loop to traverse columns ; tri [ i ] would store the possible combinations of sum of the paths ; array at n - 1 index ( tri [ i ] ) stores all possible adding combination , finding the maximum one out of them ; driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSum ( int tri [ ] [ 3 ] , int n ) { if ( n > 1 ) tri [ 1 ] [ 1 ] = tri [ 1 ] [ 1 ] + tri [ 0 ] [ 0 ] ; tri [ 1 ] [ 0 ] = tri [ 1 ] [ 0 ] + tri [ 0 ] [ 0 ] ; for ( int i = 2 ; i < n ; i ++ ) { tri [ i ] [ 0 ] = tri [ i ] [ 0 ] + tri [ i - 1 ] [ 0 ] ; tri [ i ] [ i ] = tri [ i ] [ i ] + tri [ i - 1 ] [ i - 1 ] ; for ( int j = 1 ; j < i ; j ++ ) { if ( tri [ i ] [ j ] + tri [ i - 1 ] [ j - 1 ] >= tri [ i ] [ j ] + tri [ i - 1 ] [ j ] ) tri [ i ] [ j ] = tri [ i ] [ j ] + tri [ i - 1 ] [ j - 1 ] ; else tri [ i ] [ j ] = tri [ i ] [ j ] + tri [ i - 1 ] [ j ] ; } } int max = tri [ n - 1 ] [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { if ( max < tri [ n - 1 ] [ i ] ) max = tri [ n - 1 ] [ i ] ; } return max ; } int main ( ) { int tri [ 3 ] [ 3 ] = { { 1 } , { 2 , 1 } , { 3 , 3 , 2 } } ; cout << maxSum ( tri , 3 ) ; return 0 ; }