1 条题解
-
0
C++ :
#include<bits/stdc++.h> using namespace std; const int N=300010; int q[N],s[N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { int x; cin>>x; s[i]=s[i-1]+x; //计算前缀和 } int hh=0,tt=-1; //清空数组 q[++tt]=0; //s[0] int res=-2e9; for(int i=1;i<=n;i++) { while(hh<=tt&&i-q[hh]>m) hh++; //队列中有元素,且在加入了当前元素以后会超过窗口 res=max(res,s[i]-s[q[hh]]); //以当前元素结尾的长度不超过m的子序列和 while(hh<=tt&&s[q[tt]]>=s[i]) tt--; //更新单调队列 q[++tt]=i; //将当前元素加入队列 } cout<<res; return 0; }
- 1
信息
- ID
- 773
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者