Maximum weight path ending at any element of last row in a matrix | Function which return the maximum weight path sum ; create 2D matrix to store the sum of the path ; Initialize first column of total weight array ( dp [ i to N ] [ 0 ] ) ; Calculate rest path sum of weight matrix ; find the max weight path sum to reach the last row ; return maximum weight path sum ; Driver program
function maxCost ( mat , N ) { let dp = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { dp [ i ] = new Array ( N ) ; for ( let j = 0 ; j < N ; j ++ ) { dp [ i ] [ j ] = 0 ; } } 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 i = 1 ; i < N ; i ++ ) for ( let j = 1 ; j < i + 1 && j < N ; j ++ ) dp [ i ] [ j ] = mat [ i ] [ j ] + Math . max ( dp [ i - 1 ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) ; let result = 0 ; for ( let i = 0 ; i < N ; i ++ ) if ( result < dp [ N - 1 ] [ i ] ) result = dp [ N - 1 ] [ i ] ; return result ; } let mat = [ [ 4 , 1 , 5 , 6 , 1 ] , [ 2 , 9 , 2 , 11 , 10 ] , [ 15 , 1 , 3 , 15 , 2 ] , [ 16 , 92 , 41 , 4 , 3 ] , [ 8 , 142 , 6 , 4 , 8 ] ] ; let N = 5 ; document . write ( " " + maxCost ( mat , N ) ) ;