MAXSUBARR - Editorial

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:

Maximum sum subarray

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:])))
1 Like

What is wrong with below code?

#include <bits/stdc++.h>
#define int long long int

int maxSubArray(std::vector<int>& nums) {
    auto max_sum = INT_MIN, sum = 0;
    for (auto n : nums)
    {
        sum = std::max(n, sum + n);
        max_sum = std::max(max_sum, sum);
        //cout<<sum<<" "<<max_sum<<" \n";
    }

    return max_sum;
}

void solve(){
    int n;
    std::cin >> n;
    std::vector <int> a(n);
    for(auto &i:a){
        std::cin >> i;
    }

    int m;
    std::cin >> m;
    std::vector <int> b(m);
    for(auto &i:b){
        std::cin >> i;
    }

    //Find all positive element of array b
    int s = 0;
    for(auto &i:b){
        if(i > 0)
            s += i;
    }

    int ans = std::max(0ll, maxSubArray(a));
    a.push_back(s);
    ans = std::max(ans, maxSubArray(a));
    a.pop_back();
    std::reverse(a.begin(), a.end());
    a.push_back(s);
    ans = std::max(ans, maxSubArray(a));

    std::cout << ans << "\n";
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}

I don’t really understand why my code failed test cases, I did pretty much the same thing the question asked us to.

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

int max_sum(vector<int>& arr){//kadane's algorithm
    int sum_so_far = 0, max_sum = 0;
    for(int i = 0; i < arr.size(); i++){
        sum_so_far += arr[i];
        if(sum_so_far < 0){
            sum_so_far = 0;
        }
        if(sum_so_far > max_sum){
            max_sum = sum_so_far;
        }
    }
    return max_sum;
}

int max_subarr(vector<int>& A, vector<int>& B, int m, int n){
    int sum_B = 0;
    for(int i = 0; i < B.size(); i++){//sum of all positive integers in B
        if(B[i] > 0)sum_B += B[i];
    }
    //perform kadane's on array twice, once with sum_b at 0th index and once with it at nth index
    A.insert(A.begin(), sum_B);
    int sum1 = max_sum(A);
    A.erase(A.begin());
    A.push_back(sum_B);
    int sum2 = max_sum(A);
    return max(sum1, sum2);
}

int main() {
	// your code goes here
	int t;
	cin >> t;
	while(t--){
	    int n1, n2;
	    cin >> n1;
	    vector<int> arr1;
	    for(int i = 0; i < n1; i++){
	        int x;
	        cin >> x;
	        arr1.push_back(x);
	    }
	    cin >> n2;
	    vector<int> arr2(n2, -1);
	    for(int i = 0; i < n2; i++){
	        int x;
	        cin >> x;
	        arr2.push_back(x);
	    }
	    cout << max_subarr(arr1, arr2, n1, n2) << endl;
	}
	return 0;
}

whats wrong with my code. All test cases passed except last one

#include
using namespace std;
#include <bits/stdc++.h>
#define ll long long
void solve()
{
ll n;cin>>n;
vector v(n);
for(ll i=0;i<n;i++)
{
cin>>v[i];
}
ll a;cin>>a;
vector p(a);
for(ll i=0;i<a;i++)
cin>>p[i];
ll max_so_far = LONG_MIN, max_ending_here = 0;

for (ll i = 0; i < n; i++) {
    max_ending_here = max_ending_here + v[i];
    if (max_so_far < max_ending_here)
        max_so_far = max_ending_here;

    if (max_ending_here < 0)
        max_ending_here = 0;
}

ll sum1=max_so_far;

ll max_so_far1 = LONG_MIN, max_ending_here1 = 0;

for (ll i = 0; i < a; i++) {
    max_ending_here1 = max_ending_here1 + p[i];
    if (max_so_far1 < max_ending_here1)
        max_so_far1 = max_ending_here1;

    if (max_ending_here1 < 0)
        max_ending_here1 = 0;
}
ll sum2=max_so_far1;
if(sum1<0 || sum2<0)
{
if(sum1>sum2)
cout<<sum1<<endl;
else
cout<<sum2<<endl;
}

else
cout<<sum1+sum2<<endl;

}
int main() {
ll t;
cin>>t;
while(t–)
{
solve();
}
// your code goes here
return 0;
}

@admin
Solution: 76134503 | CodeChef
This solution from another user was adjudged correct.

However, the editorialist’s code and this user’s code gave different answers when I gave this input:

1
10
-1 -2 -3 6 7 8 -8 -5 -4 -1
3
1 -1 -1

How is it possible that 2 correct codes give different answer on this question?
Submissions might need re-evaluation.

5 Likes

here don’t give size or if you are initializing with size then don’t pushback. Just like you did for arr1

Yes I think the same.
The test cases are weak for this question.

1 Like

In my opinion, the submissions for this questions should be re-evaluated.
Many people have skipped the case when the sum of any subarray of A other then that which contains first or last element has greater sum than that of the (subarray of A containing first or last element and having greater sum + value of all positive elements of array B (if present, otherwise 0))
A simple test case for it is-
3
-1 1 -1
1
-1
The answer for this test case should be 1 but many accepted code are giving output 0 on this test case.

2 Likes

Weak Test Cases
Solution: 76163617 | CodeChef
I was looking at others solution and it was all correct. But it was wrong. Some testcases are missing to judge the code.
what if test case is as follow:
7
-10 -25 20 30 40 -25 -20
4
5 -2 -3 4

Answer should be 90 for maximum subarray. But according to that solution output will be 64.
@admin @arpit121 , @tabr , @iceknight1093 look into this.

3 Likes

need to use long long at suitable places

#include <bits/stdc++.h>
#define int long long int

long long maxSubArray(std::vector<long long>& nums) {
    long long max_sum = INT_MIN, sum = 0;
    for (auto n : nums)
    {
        sum = std::max(n, sum + n);
        max_sum = std::max(max_sum, sum);
        //cout<<sum<<" "<<max_sum<<" \n";
    }

    return max_sum;
}

void solve(){
    int n;
    std::cin >> n;
    std::vector <long long> a(n);
    for(auto &i:a){
        std::cin >> i;
    }

    int m;
    std::cin >> m;
    std::vector <long long> b(m);
    for(auto &i:b){
        std::cin >> i;
    }

    //Find all positive element of array b
    long long s = 0;
    for(auto &i:b){
        if(i > 0)
            s += i;
    }

    long long ans = std::max(0ll, maxSubArray(a));
    a.push_back(s);
    ans = std::max(ans, maxSubArray(a));
    a.pop_back();
    std::reverse(a.begin(), a.end());
    a.push_back(s);
    ans = std::max(ans, maxSubArray(a));

    std::cout << ans << "\n";
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}

This would work

sum can exceed int so use long long

@klu_2100030218 please check the solution logic I think it is not correct

Hey, I suppose you are also including empty subarrays in the questions, eg:
For this test case:
1
4
-1 -2 -3 -4
4
-4 -5 -2 -5

The answer should be -1 if empty subarrays are not allowed and 0 otherwise. The editorialist’s code is giving 0 as answer which means empty subarrays are allowed right, so that arrays with all negatives give 0 as max subarray sum??

1 Like

Did you see 2nd line I have #define int to long long int, Please someone tell me why my code fails?? Took 2 hours still couldn’t find my mistake, @admin @arpit121 @tabr @iceknight1093

This gives AC, my mistake was declaring max_sum and sum to auto

#include <bits/stdc++.h>
#define int long long int

int maxSubArray(std::vector<int>& nums) {
    int max_sum = INT_MIN, sum = 0;
    for (auto n : nums)
    {
        sum = std::max(n, sum + n);
        max_sum = std::max(max_sum, sum);
        //cout<<sum<<" "<<max_sum<<" \n";
    }

    return max_sum;
}

void solve(){
    int n;
    std::cin >> n;
    std::vector <int> a(n);
    for(auto &i:a){
        std::cin >> i;
    }

    int m;
    std::cin >> m;
    std::vector <int> b(m);
    for(auto &i:b){
        std::cin >> i;
    }

    //Find all positive element of array b
    int s = 0;
    for(auto &i:b){
        if(i > 0)
            s += i;
    }

    int ans = std::max(0ll, maxSubArray(a));
    a.push_back(s);
    ans = std::max(ans, maxSubArray(a));
    a.pop_back();
    std::reverse(a.begin(), a.end());
    a.push_back(s);
    ans = std::max(ans, maxSubArray(a));

    std::cout << ans << "\n";
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}

https://www.codechef.com/viewsolution/76192417

This solution give wrong answer on the following test case:
1
7
-2 -9 -7 105 -6 -5 -9
4
1 2 3 0

It gives 93 as answer , but answer should be 105

Also what is wrong in my code, i used kadane algo and also find the start and end index of max sum subarray in arrA , then found min sum of negative elements in arrA before start and after end , then added bsum to the one with minimum sum + maxsum of arrA

#include
#include
#include
#include
#include
using namespace std;

long long maxSubarraySum(int arr[], int n,int *a,int *b){

    // Your code here
   int totalmax=-9999999;
   int globalstart=0;
   int globalend=n-1;
    int  localmax=0;
    int lstart=0;
    int lend=n-1;
    for(int i=0;i<n;i++){
        if(localmax+arr[i]<arr[i]){
            lstart=i;
        }else{
            lend=i;
        }
       localmax=max(localmax+arr[i],arr[i]);
       
       if(localmax>totalmax){
        globalstart=lstart;
        globalend=lend;
        
           totalmax=localmax;
           
           
       }
    }
    *a=globalstart;
    *b=globalend;
    return totalmax;
    
}

int main()
{
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
int arra[n];

    for (int i = 0; i < n; i++)
    {
        cin >> arra[i];
    }
    int m;
    cin >> m;
    int arrb[m];
    int sum=0;
    for (int i = 0; i < m; i++)
    {
        cin >> arrb[i];
        if(arrb[i]>0){
            sum+=arrb[i];
        }
    }
    int start=0;
    int end=n-1;
     int maxsum= maxSubarraySum(arra,n,&start,&end);
    
  
    if(start==0 ||end==n-1){
        if(maxsum<0){
        maxsum=0;}
       cout<<sum+maxsum<<endl;
    }
    
    else{
        int startsum=0;int endsum=0;
        for(int i=0;i<start;i++){
            startsum=startsum+arra[i];
        }
        for(int i=end+1;i<n;i++){
            endsum=endsum+arra[i];

        }
        int finalsum=max(max(startsum+sum,endsum+sum),0);
        cout<<max(finalsum+maxsum,sum)<<endl;
        
    }
}

}

yo i was able to solve at 0.03 sec :slight_smile:

this is my code

ll test(vectora, ll n){

ll max_so_far = INT_MIN, max_ending_here = 0;

for(int i=0; i<n; i++){

    max_ending_here = max_ending_here + a[i];

    if(max_so_far< max_ending_here) max_so_far = max_ending_here;

    if(max_ending_here<0) max_ending_here = 0;

}

return max_so_far;

}

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//this is fast I/O (inputput output) use header file <cstdio>

ll t; cin>>t;

while(t--){

    ll n; cin>>n;

    //deque<ll>a;

    vector<ll>a(n);

    //vector<ll>v;

    for(int i=0; i<n; i++) {

        cin>>a[i];

        //v.push_back(a[i]);

    }

    ll m;cin>>m;

    ll b[m];

    for(int i=0;i<m; i++) cin>>b[i];

    ll sum = 0, max_sum_front = 0, max_sum_back = 0;        // max subarray front and back

    for(int i=0; i<m; i++){

        if(b[i]>0) sum+=b[i];

    }

    ll max_subarray_sum = test(a,n);        //maximum subarray has been found using Kadane's algorithm

    ll sum_back = sum;

    for(int i=0; i<n; i++){

        sum+=a[i];

        if(sum>max_sum_front) max_sum_front = sum;

    }

    for(int i=n-1; i>=0; i--){

        sum_back +=a[i];

        if(sum_back>max_sum_back) max_sum_back = sum_back;

    }

    ll ans = max({max_subarray_sum, max_sum_front, max_sum_back });

    cout<<ans<<endl;

}

return 0;

}

hey @arpit121 i think u forgot the testcase where array A contains all negative integers except -1
and array B contains -1
my submission was passed all testcases
but when i tried a = [-6,-5,-4] b=[-1,-2]
its gives answer as -4 when it should be -1

please look into it!