Maximize path sum from top | Javascript program to implement the above approach ; Function to get the maximum path sum from top - left cell to all other cells of the given matrix ; Store the maximum path sum ; Loop to create 2D array using 1D array ; Base case ; Compute the value of dp [ i ] [ j ] using the recurrence relation ; Prlet maximum path sum from the top - left cell ; Driver Code
let SZ = 100 ; function pathSum ( mat , N , M ) { let dp = new Array ( N ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } dp [ 0 ] [ 0 ] = mat [ 0 ] [ 0 ] ; for ( let i = 1 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = mat [ i ] [ 0 ] + dp [ i - 1 ] [ 0 ] ; } for ( let j = 1 ; j < M ; j ++ ) { dp [ 0 ] [ j ] = mat [ 0 ] [ j ] + dp [ 0 ] [ j - 1 ] ; } for ( let i = 1 ; i < N ; i ++ ) { for ( let j = 1 ; j < M ; j ++ ) { dp [ i ] [ j ] = mat [ i ] [ j ] + Math . max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; } } for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 0 ; j < M ; j ++ ) { document . write ( dp [ i ] [ j ] + " " ) ; } document . write ( " " ) ; } } let mat = [ [ 3 , 2 , 1 ] , [ 6 , 5 , 4 ] , [ 7 , 8 , 9 ] ] ; let N = 3 ; let M = 3 ; pathSum ( mat , N , M ) ;