Maximum Prefix Sum possible by merging two given arrays

#include <bits/stdc++.h>

  

#define int long long

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;

}

Let's block ads! (Why?)