Maximum Prefix Sum possible by merging two given arrays | C ++ implementation of above approach ; Stores the dp states ; Recursive Function to calculate the maximum prefix sum ontained by merging two arrays ; If subproblem is already computed ; If x >= N or y >= M ; If x < N ; If y < M ; Otherwise ; Driver Code
#include <bits/stdc++.h> NEW_LINE #define int  long long NEW_LINE using namespace std ; map < pair < int , int > , int > dp ; int maxPreSum ( vector < int > a , vector < int > b , int x , int y ) { if ( dp . find ( { x , y } ) != dp . end ( ) ) return dp [ { x , y } ] ; if ( x == a . size ( ) && y == b . size ( ) ) return 0 ; int curr = dp [ { x , y } ] ; if ( x == a . size ( ) ) { curr = max ( curr , b [ y ] + maxPreSum ( a , b , x , y + 1 ) ) ; } else if ( y == b . size ( ) ) { curr = max ( curr , a [ x ] + maxPreSum ( a , b , x + 1 , y ) ) ; } else { curr = max ( { curr , a [ x ] + maxPreSum ( a , b , x + 1 , y ) , b [ y ] + maxPreSum ( a , b , x , y + 1 ) } ) ; } return dp [ { x , y } ] = curr ; } signed main ( ) { vector < int > A = { 2 , 1 , 13 , 5 , 14 } ; vector < int > B = { -1 , 4 , -13 } ; cout << maxPreSum ( A , B , 0 , 0 ) << endl ; return 0 ; }