Max Sum of Max-K-sub-sequence 单调队列

题目传送门

题意：给定一个环形数组，要确定 长度 $\le$ $k$ 的连续子段的和的最大值。

首先解决环形数组问题：将数组长度开为两倍，收尾相连即可。
然后解决有长度限制的最大连续子段和问题：我们先求一下前缀和 sum[i] ， 然后从头到尾遍历数组，以当前 i为区间最后一个值， 易知最大连续子段和即为sum[i] - 该区间范围内的最小前缀和，怎样快速得到该区间的最小前缀和呢，可以用单调队列来维护。

AC代码：

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int>a(2 * n + 10), sum(2 * n + 10);
    int ans = -2e9, al = 0, ar = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if(a[i] > ans) ans = a[i], al = i, ar = i;
        a[i + n] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + a[i];
    vector<int>q(2 * n + 10);
    int hh = 1, tt = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        int tmp = i - 1; // 注意这里我们要维护的终点是i-1
        if (hh <= tt && tmp - k + 1 > q[hh]) hh++;
        while (hh <= tt && sum[tmp] < sum[q[tt]]) tt--;
        q[++tt] = tmp;
        if(sum[i] - sum[q[hh]] > ans)
        {
            ans = sum[i] - sum[q[hh]];
            al = (q[hh] + 1) % n;
            ar = i % n;
            if(al == 0) al = n;
            if(ar == 0) ar = n;
        }
    }
    cout << ans <<" "<<al<<" "<<ar << endl;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}