INTINT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: prnv10
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic programming

PROBLEM:

You’re given two arrays A and B, both of length N.
Find the maximum possible sum obtainable by choosing one subarray from A and one subarray from B, such that the subarrays intersect.

EXPLANATION:

The subarrays we choose have to intersect somewhere.
Suppose they intersect at index i.
Once this is fixed, observe that we basically have two independent problems: maximizing the subarray sum in A and maximizing the subarray sum in B.
The only constraint is that the subarrays we choose for A and B must both include index i.

Let’s try to solve the problem just for array A.
That is, if we have a fixed index i, what’s the maximum possible sum of a subarray including this index?

To answer this, we’ll use dynamic programming.
Note that a subarray containing index i can be thought of as joining a subarray ending at i to a subarray starting at i.
The subarrays starting/ending at i are independent of each other (apart from containing i, of course), so they can be maximized separately.

So, we can do the following:

  • Let L_i denote the maximum possible sum of a subarray of A ending at index i.
  • Let R_i denote the maximum possible sum of a subarray of A starting at index i.

Computing these values is fairly straightforward.
For example, L_i = A_i + \max(0, L_{i-1}), because we’re forced to always take A_i and then we either take nothing, or extend it with a subarray ending at index i-1 (whose best answer is L_{i-1} by definition).
Similarly, we have R_i = A_i + \max(0, R_{i+1}).

The maximum possible subarray sum including index i is then (L_i + R_i - A_i), where we subtract A_i because it’s being added in both L_i and R_i.
Alternately you can use something like (L_i + \max(0, R_{i+1})) by considering ending at i and (maybe) starting at i+1; either way once the arrays L and R are known the answer for a given index can be found in constant time.

Let S_i denote the maximum subarray sum in A that includes index i.
As seen above, this can be computed for all i in linear time.

Similarly, let T_i denote the maximum subarray sum in B that includes index i.

The answer is then simply the maximum of (S_i + T_i) across all indices i.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector a(n, 0), b(n, 0);
        for (int &x : a) cin >> x;
        for (int &x : b) cin >> x;
        
        vector<ll> prea(n), preb(n);
        vector<ll> sufa(n), sufb(n);
        for (int i = 0; i < n; ++i) {
            prea[i] = a[i], preb[i] = b[i];
            if (i > 0) prea[i] += max(0ll, prea[i-1]), preb[i] += max(0ll, preb[i-1]);
        }
        for (int i = n-1; i >= 0; --i) {
            sufa[i] = a[i], sufb[i] = b[i];
            if (i+1 < n) sufa[i] += max(0ll, sufa[i+1]), sufb[i] += max(0ll, sufb[i+1]);
        }
        
        ll ans = -1e18;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, prea[i] + sufa[i] - a[i] + preb[i] + sufb[i] - b[i]);
        }
        cout << ans << '\n';
    }
}
1 Like