Maximum sum path in a matrix from top to bottom and back | Input matrix ; DP matrix ; Function to return the sum of the cells arr [ i1 ] [ j1 ] and arr [ i2 ] [ j2 ] ; Recursive function to return the required maximum cost path ; Column number of second path ; Base Case ; If already calculated , return from DP matrix ; Recurring for neighbouring cells of both paths together ; Saving result to the DP matrix for current state ; set initial value
let n = 4 , m = 4 ; let arr = [ [ 1 , 0 , 3 , - 1 ] , [ 3 , 5 , 1 , - 2 ] , [ - 2 , 0 , 1 , 1 ] , [ 2 , 1 , - 1 , 1 ] ] ; let cache = new Array ( 5 ) ; for ( let i = 0 ; i < 5 ; i ++ ) { cache [ i ] = new Array ( 5 ) ; for ( let j = 0 ; j < 5 ; j ++ ) { cache [ i ] [ j ] = new Array ( 5 ) ; for ( let k = 0 ; k < 5 ; k ++ ) { cache [ i ] [ j ] [ k ] = - 1 ; } } } function sum ( i1 , j1 , i2 , j2 ) { if ( i1 == i2 && j1 == j2 ) { return arr [ i1 ] [ j1 ] ; } return arr [ i1 ] [ j1 ] + arr [ i2 ] [ j2 ] ; } function maxSumPath ( i1 , j1 , i2 ) { let j2 = i1 + j1 - i2 ; if ( i1 >= n i2 >= n j1 >= m j2 >= m ) { return 0 ; } if ( cache [ i1 ] [ j1 ] [ i2 ] != - 1 ) { return cache [ i1 ] [ j1 ] [ i2 ] ; } let ans = Number . MIN_VALUE ; ans = Math . max ( ans , maxSumPath ( i1 + 1 , j1 , i2 + 1 ) + sum ( i1 , j1 , i2 , j2 ) ) ; ans = Math . max ( ans , maxSumPath ( i1 , j1 + 1 , i2 ) + sum ( i1 , j1 , i2 , j2 ) ) ; ans = Math . max ( ans , maxSumPath ( i1 , j1 + 1 , i2 + 1 ) + sum ( i1 , j1 , i2 , j2 ) ) ; ans = Math . max ( ans , maxSumPath ( i1 + 1 , j1 , i2 ) + sum ( i1 , j1 , i2 , j2 ) ) ; cache [ i1 ] [ j1 ] [ i2 ] = ans ; return ans ; } document . write ( maxSumPath ( 0 , 0 , 0 ) ) ;