题目分析

注意本题要找的是连续的最长子序列。如果只是找任意一个子序列的话，可直接排序取最大的 $\le m$ （因为有负数存在）个数即可。

暴力枚举

暴力枚举其实就是对问题的解空间进行遍历，找出最优的方案并记录其结果。因为要取连续且超度不超过 $m$ 的子序列，本题的枚举方式可为 以每个元素为结尾的长度不超过 $m$ 的连续子序列。

这样做的时间复杂度为 $O(n \times m)$。时间上限为 $9 \times 10^{10}$，显然是达不到要求的。

找出问题可优化的地方

首先，肯定要枚举到每个位置的数，所以对于枚举以每个数为结尾的方案是不可优化的。

其次，由于要判断的是最大和，当枚举以元素 $i$ 为结尾的长度不超过 $m$ 的连续子序列时，每一种情况都是一个区间和。而区间和的计算可以通过前缀和来快速计算。

对于区间 $[l,r]$ 的和的计算公式为 s[r] - s[l-1]。当 右端点固定 时（$s[r]$ 固定），要想使以元素 $i$ 为结尾的元素的区间和最大，相当于要让 $s[l-1]$ 的值最小。因为区间的长度为 $[1,m]$，所以 $r-m \le l-1 < r$。

于是问题就转换为要在 $r$ 前面的一个固定长度的区间 $[r-m,r-1]$ 中找到最小值，可以通过单调队列来实现。

方法一

通过上面的分析，对每个位置 $i$ 都维护长度为 $m$ 的区间 $[i-m,i-1]$ 中元素的最小值，然后用当前位置 $i$ 的前缀和减去单调队列中维护的前面的最小前缀和即可得到以 $i$ 为结尾的长度不超过 $m$ 的最大子序列的和。

对位置 $i$ 的计算完成后，需要将其加入单调队列。

全局维护一个最大连续子序列和。

代码实现

#include <iostream>

using namespace std;

const int N = 300010;
int s[N];
int q[N];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%d", &s[i]), s[i] += s[i - 1];

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

    cout << ans << endl;

    return 0;
}

时间复杂度为 $O(n)$。