Auto comment: topic has been updated by NoobCoder1998 (previous revision, new revision, compare).

Kadane along with sliding window should do the trick in O(N)

Ps: Can you provide problem name or number.

The best solution I can think of:

You can solve it using DP. Let $$$dp[i][x]$$$ be the maximum sum of a subarray starting at index $$$i$$$, where:

• $$$x=0$$$ means the replaced subarray begins after the current index.
• $$$x=1$$$ means this index is part of the replaced subarray.
• $$$x=2$$$ means the replaced subarray ends before the current index.

If $$$x=0$$$, we can:

• Decide to start the replaced subarray on the current element ($$$dp[i][1]$$$),
• Add the current value (arr1[i]) to the sum and go to the next element ($$$dp[i+1][0]+arr1[i]$$$), or
• Decide not to add any more elements to the final subarray (the one with the maximum sum) ($$$0$$$).

If $$$x=1$$$, we can:

• Decide to end the replaced subarray on the previous element (so this will be the first element that won't be a part of the subarray) ($$$dp[i][2]$$$),
• Add the current value (arr2[i]) to the sum and go to the next element ($$$dp[i+1][1]+arr2[i]$$$), or
• Decide not to add any more elements to the final subarray (the one with the maximum sum) ($$$0$$$).

If $$$x=2$$$, we can:

• Add the current value (arr1[i]) to the sum and go to the next element ($$$dp[i+1][2]+arr1[i]$$$), or
• Decide not to add any more elements to the final subarray (the one with the maximum sum) ($$$0$$$).

So:
$$$dp[i][0]=max(dp[i][1],dp[i+1][0]+arr1[i],0)$$$
$$$dp[i][1]=max(dp[i][2],dp[i+1][1]+arr2[i],0)$$$
$$$dp[i][2]=max(dp[i+1][2]+arr1[i],0)$$$
Base case: $$$dp[n][x]=0$$$

The answer is the maximum value of $$$dp[i][0]$$$ for all $$$i$$$.

Total complexity: $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1e5;
const ll INF=1e18;

ll n, arr1[N], arr2[N];

ll ans[N][3];
ll solve(ll i, ll x){
    if(i==n) return 0;
    else if(ans[i][x]!=-INF) return ans[i][x];
    else if(x==0) return ans[i][x]=max(max(solve(i,1), solve(i+1,0)+arr1[i]), 0ll);
    else if(x==1) return ans[i][x]=max(max(solve(i,2), solve(i+1,1)+arr2[i]), 0ll);
    else  return ans[i][x]=max(solve(i+1,2)+arr1[i], 0ll);
}

int main(){
    cin>>n;
    for(ll i=0; i<n; i++){
        cin>>arr1[i];
    }
    for(ll i=0; i<n; i++){
        cin>>arr2[i];
    }
    
    for(ll i=0; i<n; i++){
        ans[i][0]=-INF;
        ans[i][1]=-INF;
        ans[i][2]=-INF;
    }
    
    ll ans=-INF;
    for(ll i=0; i<n; i++){
        ans=max(ans,solve(i,0));
    }
    cout<<ans<<endl;
}

Hope it helps!

I am not sure whether this is correct or not, but I think you can use dp and Kadane algorithm

the dp states are i and j where i is the index and j is $$$0$$$ if you haven't taken any element from $$$b$$$, $$$1$$$ if the previous element was from $$$b$$$ (i.e. you can still take element $$$i$$$ from $$$b$$$) and $$$2$$$ if you can no longer take elements from $$$b$$$

$$$dp_{sum}[i][j]$$$ is the sum until state $$$i, j$$$, $$$dp_{max}[i][j]$$$ is the maximum subarray sum till state $$$i, j$$$.

here is my implementation to this:

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    const int canTake = 0, taking = 1, cant = 2;
    vector dpSum(n + 1, vector<ll>(3));
    vector dpMax(n + 1, vector<ll>(3));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (j == canTake){
                dpSum[i][canTake] = dpSum[i - 1][canTake];
                if (a[i] > dpSum[i][canTake]){
                    dpSum[i][canTake] = a[i];
                } else {
                    dpSum[i][canTake] += a[i];
                }
                dpMax[i][canTake] = max(dpMax[i - 1][canTake], dpSum[i][canTake]);
            } else if (j == taking){
                dpSum[i][taking] = max(dpSum[i - 1][canTake], dpSum[i - 1][taking]);
                if (b[i] > dpSum[i][taking]){
                    dpSum[i][taking] = b[i];
                } else {
                    dpSum[i][taking] += b[i];
                }
                dpMax[i][taking] = max({dpMax[i - 1][canTake], dpMax[i - 1][taking], dpSum[i][taking]});
            } else {
                dpSum[i][cant] = max(dpSum[i - 1][cant], dpSum[i - 1][taking]);
                if (a[i] > dpSum[i][cant]){
                    dpSum[i][cant] = a[i];
                } else {
                    dpSum[i][cant] += a[i];
                }
                dpMax[i][cant] = max({dpMax[i - 1][cant], dpMax[i - 1][taking], dpSum[i][cant]});
            }
        }
    }
    cout << max({dpMax[n][0], dpMax[n][1], dpMax[n][2]}) << endl;
}

I tried it on some randomly generated tests and it works