推荐博客:http://t.csdn.cn/fkIau
解题思路:
1:假设s[i]为a[i]的前缀和数组若要求出:一段长度不超过 m 的连续子序列,使得子序列中所有数的和最大。
2:即求出s[i] - s[i - m + 1](m = 1, ..., m)的最大值
3:因为s[i]已固定, 即求出s[i - m + 1]最小值即可;
4:这里需要一个队列维护一个长度不大于m的数组,
当队列队尾的元素大于等于当前需要插入的数时,就可以把队尾删除
即维护了一个单调上升的单调队列
每次取出对头元素即为最小值
代码如下:
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 300010;
int a[N];
LL s[N];
int q[N], hh, tt;
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
LL res = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
{
while (i - q[hh] > m) hh ++ ;//当队列中的元素数量多于m时弹出对头,
//这里本应该是i - q[hh] + 1的但因为上次循环i加了一次所以需要少减一次
res = max(res, s[i] - s[q[hh]]);//记录每次 循环的对最大值
while (hh <= tt && s[q[tt]] >= s[i]) tt -- ;//当队列不空切队尾元素大于s[i]时弹出队尾;
q[++ tt] = i;//经过上面的while循环此时队列中的元素一定都小于i,将i插入队尾
}
cout << res << endl;
return 0;
}