题目描述
输入一个长度为 的整数序列 ，从中找出一段不超过 的连续子序列（区间），使得这个序列的和最大。选出的区间可以为空。
输入描述
第一行两个数 ，第二行 个整数 表示这个数列。
输出描述
一个整数表示答案。
样例输入
6 3
1 -3 5 1 -2 3
样例输出
6
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 1000005
ll n, m, ans = 0;
ll a[MAXN], sum[MAXN];
deque<ll> q;
int main() {
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
q.emplace_back(0);
for (ll i = 1; i <= n; i++) {
while (!q.empty() && sum[i] < sum[q.back()]) {
q.pop_back();
}
q.emplace_back(i);
while (!q.empty() && q.front() < i - m) {
q.pop_front();
}
ans = max(ans, sum[i] - sum[q.front()]);
}
cout << ans;
return 0;
}