Maximum path sum in an Inverted triangle | SET 2 | Java 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
class GFG { static int N = 3 ; static int maxPathSum ( int tri [ ] [ ] ) { 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 ] += Math . max ( tri [ i + 1 ] [ j ] , tri [ i + 1 ] [ j - 1 ] ) ; else tri [ i ] [ j ] += tri [ i + 1 ] [ j ] ; ans = Math . max ( ans , tri [ i ] [ j ] ) ; } } return ans ; } public static void main ( String [ ] args ) { int tri [ ] [ ] = { { 1 , 5 , 3 } , { 4 , 8 , 0 } , { 1 , 0 , 0 } } ; System . out . println ( maxPathSum ( tri ) ) ; } }