PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Arpit Dutt Dixit
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
PROBLEM:
You have two arrays A and B. In one move, you can choose either the first or last element of B, and move it to either the front or back of A.
What is the maximum possible sum of a subarray in the final array?
EXPLANATION:
We’d like a large subarray sum, so it makes sense to ignore negative elements from B as much as possible and take as many positive elements as we can.
One obvious way to do this is to just move all the negative elements to one side and positive elements to the other — for example, move all negative elements of B to the back of A, and all positive elements of B to the front of A. Alternately, we can move all the negative elements to the front and the positive ones to the back.
It turns out that these are the only two cases we need to consider!
Proof
This can be proved by analyzing what the final answer looks like.
- If the maximum subarray doesn’t contain any elements from B, it doesn’t matter how the distribution is done, since subarrays of A remain unchanged.
- If the maximum subarray doesn’t contain any elements from A, the best we can do is obviously just the sum of all positive elements in B, which both cases of ours cover.
- Finally, suppose the maximum subarray includes elements from both A and B. Note that since elements of B can only be inserted at the start or end, the structure of such a subarray is:
- Some elements of B and a prefix of A, or
- Some elements of B and a suffix of A
“Some elements of B” is optimally every positive integer of B, and then we choose a prefix or suffix of A with maximum sum. Note that this is exactly what our two cases cover, hence completing the proof.
There are only two cases. For each one, find the maximum subarray sum of the resulting array in linear time (this is a well-known algorithm, and is linked above in the prerequisites).
The final answer is the maximum of the two cases.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define lli long long
lli maxSubArraySum(vector<lli> a, int n)
{
lli max_tot = INT_MIN, m = 0;
for (int i = 0; i < n; i++) {
m = m + a[i];
if (max_tot < m)
max_tot = m;
if (m < 0)
m = 0;
}
return max_tot;
}
int main(){
// freopen("output.txt","r",stdin);
// freopen("output1.txt","w",stdout);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n;
vector<lli> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
cin>>m;
vector<lli> b(m);
lli p=0;
for(int i=0;i<m;i++){
cin>>b[i];
if(b[i]>0)p+=b[i];
}
long long maxx;
a.insert(a.begin(),p);
maxx=maxSubArraySum(a,n+1);
a.erase(a.begin(),a.begin()+1);
a.insert(a.begin()+n,p);
maxx=max(maxx,maxSubArraySum(a,n+1));
cout<<maxx<<endl;
}
}
Editorialist's code (Python)
def calc(a):
ans = cur = 0
for x in a:
cur = max(x, x + cur)
ans = max(ans, cur)
return ans
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
b.sort()
pos = 0
while pos < m and b[pos] < 0:
pos += 1
print(max(calc(b[pos:] + a), calc(a + b[pos:])))
