AcWing 135. 最大子序和
原题链接
简单
作者:
史一帆
,
2021-04-29 19:34:04
,
所有人可见
,
阅读 227
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 300010;
typedef long long LL;
LL s[N];
deque<int> q;
int n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
cin >> s[i];
s[i] += s[i - 1];
}
q.push_back(0);
LL res = s[1];
for (int i = 1; i <= n; i ++ )
{
if (q.front() < i - m) // 如果当前元素的下标与队头元素下标的距离超过m
q.pop_front();
if (!q.empty()) res = max(res, s[i] - s[q.front()]);
while (!q.empty() && s[i] <= s[q.back()]) // 当前元素小于队尾元素
q.pop_back();
q.push_back(i);
}
printf("%d\n", res);
return 0;
}