Maximum sum path in a matrix from top to bottom | Function to find the maximum sum path in a matrix ; If there is a single element only ; dp [ ] [ ] matrix to store the results of each iteration ; Loop to create 2D array using 1D array ; 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
function maxSum ( mat , n ) { if ( n == 1 ) return mat [ 0 ] [ 0 ] ; let dp = new Array ( n ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } let maxSum = Number . MIN_VALUE , max ; for ( let j = 0 ; j < n ; j ++ ) dp [ n - 1 ] [ j ] = mat [ n - 1 ] [ j ] ; for ( let i = n - 2 ; i >= 0 ; i -- ) { for ( let j = 0 ; j < n ; j ++ ) { max = Number . MIN_VALUE ; if ( ( ( j - 1 ) >= 0 ) && ( max < dp [ i + 1 ] [ j - 1 ] ) ) max = dp [ i + 1 ] [ j - 1 ] ; if ( ( ( j + 1 ) < n ) && ( max < dp [ i + 1 ] [ j + 1 ] ) ) max = dp [ i + 1 ] [ j + 1 ] ; dp [ i ] [ j ] = mat [ i ] [ j ] + max ; } } for ( let j = 0 ; j < n ; j ++ ) if ( maxSum < dp [ 0 ] [ j ] ) maxSum = dp [ 0 ] [ j ] ; return maxSum ; } let mat = [ [ 5 , 6 , 1 , 7 ] , [ - 2 , 10 , 8 , - 1 ] , [ 3 , - 7 , - 9 , 11 ] , [ 12 , - 4 , 2 , 6 ] ] ; let n = 4 ; document . write ( " " + maxSum ( mat , n ) ) ;