Maximum Subarray Sum II

Given an array of n integers, your task is to find the maximum sum of values in a contiguous subarray with the length between a and b.

Example:

Input:  n = 8, a = 1, b = 2, arr = {-1, 3, -2, 5, 3, -5, 2, 2}
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1e18;

long long int maximumSubarrySumII(long long int n,
                                  long long int a,
                                  long long int b,
                                  vector<long long int> &arr)
{

    vector<long long int> ps(n + 1);
    for (long long int i = 1; i <= n; i++)
    {
        long long int x = arr[i - 1];
        ps[i] = ps[i - 1] + x;
    }
    long long int ans = -INF;
    multiset<long long int> ms;
    for (long long int i = 1; i <= n; i++)
    {
        if (i < a)
            continue;
        if (i > b)
            ms.erase(ms.find(ps[i - b - 1]));
        ms.insert(ps[i - a]);
        ans = max(ans, ps[i] - *ms.begin());
    }
    return ans;
}

int main()
{
    long long int n = 8, a = 1, b = 2;

    vector<long long int> arr = {-1, 3, -2, 5, 3, -5, 2, 2};

    cout << maximumSubarrySumII(n, a, b, arr) << "\n";

    return 0;
}