Maximum path sum 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 right to the number add the maximum of them to it ; return the top element which stores the maximum sum ; Driver Code
< ? php function maxPathSum ( $ tri , $ m , $ n ) { for ( $ i = $ m - 1 ; $ i >= 0 ; $ i -- ) { for ( $ j = 0 ; $ j <= $ i ; $ j ++ ) { if ( $ tri [ $ i + 1 ] [ $ j ] > $ tri [ $ i + 1 ] [ $ j + 1 ] ) $ tri [ $ i ] [ $ j ] += $ tri [ $ i + 1 ] [ $ j ] ; else $ tri [ $ i ] [ $ j ] += $ tri [ $ i + 1 ] [ $ j + 1 ] ; } } return $ tri [ 0 ] [ 0 ] ; } $ tri = array ( array ( 1 , 0 , 0 ) , array ( 4 , 8 , 0 ) , array ( 1 , 5 , 3 ) ) ; echo maxPathSum ( $ tri , 2 , 2 ) ; ? >