AcWing 135. Maximum subsequence sum (prefix sum + monotone queue to find the minimum value of fixed length interval)

Pre knowledge ： Monotone queue to find the minimum value of sliding window

The question ：

Given a The length is n Integer sequence of （ There may be negative ）, from Find a length that does not exceed m A continuous subsequence of , bring The sum of all numbers in a subsequence Maximum .n、m ≤ 3 * 10 ^ 5

Ideas ：

According to our experience , Calculation “ Interval and ” The problem of , Generally, it turns into “ Two prefixes and subtraction ” In the form of .

Find out first s[i] It means before in the sequence i Sum of items , be Continuous subsequences [L,R] Sum of median numbers Is equal to s[R] - s[L - 1].

that The original problem can be transformed into ： find Two positions x, y, send s[y] - s[x] Maximum , also y - x ≤ m.

Since it will Prefixes and arrays s It's all worked out , So it's easy ：

• Enumerating interval Right endpoint i ： from i = 1 Start , Enumerate from front to back i = n.

• about Each right endpoint , After fixing , We found one Left end point j, among j ∈ [i - m,i - 1] And makes s[j] Minimum （ according to Any interval [i,j + 1] Elements and be equal to s[i] - s[j], We want to Maximize the sum of intervals , Obviously send s[j] As small as possible ）.

The above process is not just one in each The interval length is m The range of Find minimum value Do you , Final , We will turn this question into Classic use of sliding windows .

take Traverse each right endpoint to find the maximum interval sum Find out , And take max, Is the answer .

Time complexity ：

$O(n)$

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 3e5 + 10;
int a[N], q[N];
int n, m;
int s[N];

int solve()
{
    
    int ans = -INT_MAX;
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; ++i)
    {
    
        if (hh <= tt && i - q[hh] > m) hh++;
        ans = max(ans, s[i] - s[q[hh]]);
        while (hh <= tt && s[q[tt]] >= s[i]) --tt;
        q[++tt] = i;
    }

    return ans;
}

signed main()
{
    
    int T = 1; //cin >> T;

    while (T--)
    {
    
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
        {
    
            scanf("%lld", &a[i]);
            s[i] = s[i - 1] + a[i];
        }

        cout << solve() << '\n';

    }

    return 0;
}