Help with Maximum Subarray Sum II from CSES

general
,
1

Link to the problem: CSES - Maximum Subarray Sum II
My Approach: I don’t really have any approach for this problem. Though I tried looking for an explanation on the internet and found one on Codeforces (Codeforces) but couldn’t understand the intended solution.

Can anyone please suggest an approach for solving this problem along with some intuitive explanation?

2

Let p_i denote the sum of the first i elements. Each subarray sum can be represented as a p_i - p_j. The question says to maximise it over all values
i,j such that a\le j-i \le b, since j-i is the number of elements in the subarray.

Let us iterate i from a to n. We want to maximise p_i - p_j, therefore we want to minimise p_j. j can be in the range i-a to i-b. Since we need to add and remove only one value, we can use a multiset to maintain the minimum value in the range by adding p_{i-a} and removing p_{i-b-1} in each iteration.

Code 
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
void solve(){
    int n,a,b;
    cin>>n>>a>>b;
    vector<ll> prefixsum(n+1);
    prefixsum[0] = 0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        prefixsum[i] = prefixsum[i-1] + x;
    }
    multiset<ll> curr;
    ll ans = -2e18;
    for(int i=a;i<=n;i++){
        if(i>b){
            curr.erase(curr.find(prefixsum[i-b-1]));
        }
        curr.insert(prefixsum[i-a]);
        ans = max(ans, prefixsum[i] - *curr.begin());
    }
    cout<<ans<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Actually, it can be solved even faster, in O(n). There is a nice data structure that allows us to find the minimum value of queue in amortised O(1). Since we only want to remove the last element, a queue can be used.

O(n) code 
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
struct minqueue{
    stack<pair<ll,ll>> front, back;
    void push(ll x){
        if(front.empty()){
            front.push({x,x});
            return;
        }
        front.push({x, min(x,front.top().second)});
    }
    void pop(){
        assert(front.size() + back.size());
        if(!back.empty()){
            back.pop();
            return;
        }
        back.push({front.top().first, front.top().first});
        front.pop();
        while(!front.empty()){
            back.push({front.top().first, min(front.top().first, back.top().second)});
            front.pop();
        }
        back.pop();
    }
    ll getmin(){
        assert(front.size() + back.size());
        if(front.empty()){
            return back.top().second;
        }
        if(back.empty()){
            return front.top().second;
        }
        return min(front.top().second, back.top().second);
    }
};
void solve(){
    int n,a,b;
    cin>>n>>a>>b;
    vector<ll> prefixsum(n+1);
    prefixsum[0] = 0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        prefixsum[i] = prefixsum[i-1] + x;
    }
    minqueue curr;
    ll ans = -2e18;
    for(int i=a;i<=n;i++){
        if(i>b){
            curr.pop();
        }
        curr.push(prefixsum[i-a]);
        ans = max(ans, prefixsum[i] - curr.getmin());
    }
    cout<<ans<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
7 Likes
3

Does that data structure has a name ? I would like to read upon it before looking at your code.

5

You can refer to the cp algorithms blog data structure is Minimum Queue using 2 stacks
https://cp-algorithms.com/data_structures/stack_queue_modification.html