最大子序和
求区间最大和首先我们想到用前缀和求解。就可以把问题转换成:找出S[j] - S[i] 最大 并且 j - i + 1 <= m
首先我们可以枚举右端点设i,当i固定了,问题就变为:找到一个左端点j使得j在[i - m , i - 1]之间,S[j]最小
这个时候我们可以想到用队列来维护这个j。
我们用一个队列保存这个序列。随着右端点向右移动,我们可以对每个i执行以下三个操作:
1.判断队头到i是否超过m
2.此时右端点是i,左端点j的最优选择
3.不断筛选队尾决策。直到对应的S小于前一个S值。然后把它作为新的决策加入
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 300010;
int n, m;
LL s[N];
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%lld", &s[i]);
s[i] += s[i - 1]; //预处理前缀和
}
int hh = 0, tt = 0; //初始化队列
q[0] = 0; //加入一个哨兵,当i不足m时,前i个数之和可以直接用来更新,这时s[l - 1]应该为0
LL res = -1e12; //记录答案
for(int i = 1; i <= n; i++)
{
while(hh <= tt && i - q[hh] > m) hh++; //滑动窗口
res = max(res, s[i] - s[q[hh]]); //更新答案
while(hh <= tt && s[q[tt]] >= s[i]) tt--; //保证队列单调递减
q[++tt] = i;
}
printf("%lld\n", res);
return 0;
}