Maximum path sum in an Inverted triangle | SET 2 | C ++ program implementation of Max sum problem in a triangle ; Function for finding maximum sum ; Loop for bottom - up calculation ; For each element , check both elements just below the number and below left to the number add the maximum of them to it ; Return the maximum sum ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  3 NEW_LINE int maxPathSum ( int tri [ ] [ N ] ) { int ans = 0 ; for ( int i = N - 2 ; i >= 0 ; i -- ) { for ( int j = 0 ; j < N - i ; j ++ ) { if ( j - 1 >= 0 ) tri [ i ] [ j ] += max ( tri [ i + 1 ] [ j ] , tri [ i + 1 ] [ j - 1 ] ) ; else tri [ i ] [ j ] += tri [ i + 1 ] [ j ] ; ans = max ( ans , tri [ i ] [ j ] ) ; } } return ans ; } int main ( ) { int tri [ N ] [ N ] = { { 1 , 5 , 3 } , { 4 , 8 , 0 } , { 1 , 0 , 0 } } ; cout << maxPathSum ( tri ) ; return 0 ; }