Maximum path sum that starting with any cell of 0 | Javascript program to find Maximum path sum start any column in row '0' and ends up to any column in row ' n - 1' ; function find maximum sum path ; create 2D matrix to store the sum of the path ; initialize all dp matrix as '0' ; copy all element of first column into ' dp ' first column ; Find maximum path sum that end ups at any column of last row ' N - 1' ; return maximum sum path ; driver code
let N = 4 ; function MaximumPath ( Mat ) { let result = 0 ; let dp = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { dp [ i ] = new Array ( N + 2 ) ; for ( let j = 0 ; j < N + 2 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i < N ; i ++ ) dp [ 0 ] [ i + 1 ] = Mat [ 0 ] [ i ] ; for ( let i = 1 ; i < N ; i ++ ) for ( let j = 1 ; j <= N ; j ++ ) dp [ i ] [ j ] = Math . max ( dp [ i - 1 ] [ j - 1 ] , Math . max ( dp [ i - 1 ] [ j ] , dp [ i - 1 ] [ j + 1 ] ) ) + Mat [ i ] [ j - 1 ] ; for ( let i = 0 ; i <= N ; i ++ ) result = Math . max ( result , dp [ N - 1 ] [ i ] ) ; return result ; } let Mat = [ [ 4 , 2 , 3 , 4 ] , [ 2 , 9 , 1 , 10 ] , [ 15 , 1 , 3 , 0 ] , [ 16 , 92 , 41 , 44 ] ] document . write ( MaximumPath ( Mat ) )