记录编号 554097 评测结果 AAAAAAAAAA
题目名称 最大子序和 最终得分 100
用户昵称 Gravatartat 是否通过 通过
代码语言 C++ 运行时间 0.162 s
提交时间 2020-09-07 21:16:21 内存使用 8.36 MiB
显示代码纯文本
#include <bits/stdc++.h>
using namespace std; 
int m,n;
struct tmp{
	int da;
	int num;
}li[400001];
deque<int> s;
int main(int argc, char** argv) {
	freopen("maxsubseqsum.in","r",stdin);
	freopen("maxsubseqsum.out","w",stdout);
	cin>>n>>m;
	li[0].da=0;
	for(int i=1;i<=n;i++){
		cin>>li[i].da;
		li[i].da+=li[i-1].da;
		li[i].num=i;
	}
	int maxs=li[1].da;
	s.push_back(1);
	for(int i=2;i<=n;i++){//i表示此时之尾 
		while(!s.empty()&&i-li[s.front()].num>m){
	    	s.pop_front();//此时在队列里的为front到i-1
		}
	  	maxs=max(maxs,li[i].da-li[s.front()].da); 
		while(!s.empty()&&li[i].da<li[s.back()].da){
			s.pop_back();
		}
		s.push_back(i);
	}
	cout<<maxs;
	return 0;
}