题意:一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。
可以用单调队列来解决这道题,我们把寻找字段和转化为前缀和之差,然后固定右端点,不断枚举左端点,使其区间内元素个数不超过m个
如果k<j且Sk>=Sj,那么k这个元素是一定不如j的
#include<bits/stdc++.h> using namespace std; const int maxx = 300010; int sum[maxx],q[maxx];//q记录下标 int main() { int n,m; while(~scanf("%d%d",&n,&m)) { int t; for(int i=1;i<=n;i++) { scanf("%d",&t); sum[i]=sum[i-1]+t; } int l=1,r=1,ans=sum[1]; for(int i=1;i<=n;i++) { while(l<=r&&q[l]<i-m)l++; ans=max(sum[i]-sum[q[l]],ans); while(l<=r&&sum[q[r]]>=sum[i])r--; q[++r]=i; } printf("%d\n",ans); } return 0; }