Help with Maximum Subarray Sum II from CSES

Link to the problem: https://cses.fi/problemset/task/1644
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 (https://codeforces.com/blog/entry/77322) but couldn’t understand the intended solution.

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

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();
}
3 Likes