最大子序和

AcWing-135-最大子序和

分析

见《进阶指南》第58页。

实现

#include <iostream>
#include <queue>
#define inf 0x7fffffff
using namespace std;

typedef long long LL;
const int N = 300010;
int n, m;
LL a[N], sum[N];
deque<int> dq;

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + a[i];

    LL res = -inf;
    dq.push_back(0); // 单调队列 + 前缀和
    for (int i = 1; i <= n; ++ i) {
        if (!dq.empty() && i - dq.front() > m) dq.pop_front();
        res = max(res, sum[i] - sum[dq.front()]);
        while (!dq.empty() && sum[dq.back()] >= sum[i]) dq.pop_back();
        dq.push_back(i);
    }
    printf("%lld", res);
    return 0;
}