Maximum sum of a path in a Right Number Triangle | 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 Code
< ? php function maxSum ( $ tri , $ n ) { if ( $ n > 1 ) $ tri [ 1 ] [ 1 ] = $ tri [ 1 ] [ 1 ] + $ tri [ 0 ] [ 0 ] ; $ tri [ 1 ] [ 0 ] = $ tri [ 1 ] [ 0 ] + $ tri [ 0 ] [ 0 ] ; for ( $ 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 ( $ 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 ] ; } } $ max = $ tri [ $ n - 1 ] [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { if ( $ max < $ tri [ $ n - 1 ] [ $ i ] ) $ max = $ tri [ $ n - 1 ] [ $ i ] ; } return $ max ; } $ tri = array ( array ( 1 ) , array ( 2 , 1 ) , array ( 3 , 3 , 2 ) ) ; echo maxSum ( $ tri , 3 ) ; ? >