Maximum sum path in a matrix from top to bottom | PHP implementation to find the maximum sum path in a matrix ; function to find the maximum sum path in a matric ; if there is a single element only ; dp [ ] [ ] matrix to store the results of each iteration ; base case , copying elements of last row ; building up the dp [ ] [ ] matrix from bottom to the top row ; finding the maximum diagonal element in the ( i + 1 ) th row if that cell exists ; adding that ' max ' element to the mat [ i ] [ j ] element ; finding the maximum value from the first row of dp [ ] [ ] ; required maximum sum ; Driver Code
< ? php $ SIZE = 10 ; function maxSum ( $ mat , $ n ) { if ( $ n == 1 ) return $ mat [ 0 ] [ 0 ] ; $ dp = array ( array ( ) ) ; $ maxSum = PHP_INT_MIN ; $ max ; for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ dp [ $ n - 1 ] [ $ j ] = $ mat [ $ n - 1 ] [ $ j ] ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { for ( $ j = 0 ; $ j < $ n ; $ j ++ ) { $ max = PHP_INT_MIN ; if ( ( ( $ j - 1 ) >= 0 ) and ( $ max < $ dp [ $ i + 1 ] [ $ j - 1 ] ) ) $ max = $ dp [ $ i + 1 ] [ $ j - 1 ] ; if ( ( ( $ j + 1 ) < $ n ) and ( $ max < $ dp [ $ i + 1 ] [ $ j + 1 ] ) ) $ max = $ dp [ $ i + 1 ] [ $ j + 1 ] ; $ dp [ $ i ] [ $ j ] = $ mat [ $ i ] [ $ j ] + $ max ; } } for ( $ j = 0 ; $ j < $ n ; $ j ++ ) if ( $ maxSum < $ dp [ 0 ] [ $ j ] ) $ maxSum = $ dp [ 0 ] [ $ j ] ; return $ maxSum ; } $ mat = array ( array ( 5 , 6 , 1 , 7 ) , array ( -2 , 10 , 8 , -1 ) , array ( 3 , -7 , -9 , 11 ) , array ( 12 , -4 , 2 , 6 ) ) ; $ n = 4 ; echo " Maximum ▁ Sum ▁ = ▁ " , maxSum ( $ mat , $ n ) ; ? >