Maximum sum path in a matrix from top to bottom and back | C ++ implementation of the approach ; 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 ; Driver code ; set initial value
#include <bits/stdc++.h> NEW_LINE using namespace std ; int n = 4 , m = 4 ; int arr [ 4 ] [ 4 ] = { { 1 , 0 , 3 , -1 } , { 3 , 5 , 1 , -2 } , { -2 , 0 , 1 , 1 } , { 2 , 1 , -1 , 1 } } ; int cache [ 5 ] [ 5 ] [ 5 ] ; int sum ( int i1 , int j1 , int i2 , int j2 ) { if ( i1 == i2 && j1 == j2 ) { return arr [ i1 ] [ j1 ] ; } return arr [ i1 ] [ j1 ] + arr [ i2 ] [ j2 ] ; } int maxSumPath ( int i1 , int j1 , int i2 ) { int 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 ] ; } int ans = INT_MIN ; ans = max ( ans , maxSumPath ( i1 + 1 , j1 , i2 + 1 ) + sum ( i1 , j1 , i2 , j2 ) ) ; ans = max ( ans , maxSumPath ( i1 , j1 + 1 , i2 ) + sum ( i1 , j1 , i2 , j2 ) ) ; ans = max ( ans , maxSumPath ( i1 , j1 + 1 , i2 + 1 ) + sum ( i1 , j1 , i2 , j2 ) ) ; ans = max ( ans , maxSumPath ( i1 + 1 , j1 , i2 ) + sum ( i1 , j1 , i2 , j2 ) ) ; cache [ i1 ] [ j1 ] [ i2 ] = ans ; return ans ; } int main ( ) { memset ( cache , -1 , sizeof ( cache ) ) ; cout << maxSumPath ( 0 , 0 , 0 ) ; return 0 ; }