涉及算法:
前缀和, 单调队列
题意简化分析为:求区间小于等于m的的最大序列和==>>用前缀和表示为【s[i] - s[j]】其中 i> j >= i - m + 1
当我们右端点确定时, 只需要在左侧区间中找一个最小的s[j]即可
此时使用单调队列即可
注意最终结果可能包含在前m个数的子区间中即s[i] - s[0], 所以队列需要初始化 que[ tt] = 0;
同时注意我们是固定右端点后寻找结果,所以判断窗口中元素是否超出实际窗口时 队列最长实际为 m - 1;
//if(hh <= tt && i - que[hh] > m) hh ;
#include<iostream>
using namespace std;
const int N = 3 * 1e5 + 10;
int n, m;
int a[N];
int que[N], hh = 0, tt = -1;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i], a[i] += a[i - 1];
int res = -1e9;
que[++ tt] = 0;
for(int i = 1; i <= n; i ++)
{
if(hh <= tt && i - que[hh] > m) hh ++;
res = max(res, a[i] - a[que[hh]]);
while(hh <= tt && a[que[tt]] >= a[i]) tt --;
que[++ tt] = i;
}
cout << res;
return 0;
}