Maximum path sum in an Inverted triangle | SET 2 | PHP 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
< ? php $ N = 3 ; function maxPathSum ( $ tri ) { global $ N ; $ ans = 0 ; for ( $ i = $ N - 2 ; $ i >= 0 ; $ i -- ) { for ( $ 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 ; } $ tri = array ( array ( 1 , 5 , 3 ) , array ( 4 , 8 , 0 ) , array ( 1 , 0 , 0 ) ) ; echo maxPathSum ( $ tri ) ; ? >