记录编号	239324	评测结果	AAAAAAAAAA
题目名称	单子序列最大和	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2016-03-20 10:11:53	内存使用	0.00 MiB

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
	const int maxn=100000 + 10;
struct cat_deque{
	int len,l,r;
	int a[maxn<<1];
	cat_deque(){
		len = 0;
		l = r = maxn;
		r--;
	}
	bool empty(){return (len==0);}
	void push_back(int x){l--;len++;a[l]=x;}
	int front(){return a[r];}
	int back(){return a[l]; }
	void pop_front(){r--;len--;}
	void pop_back(){l++;len--;}
};
namespace cat{
	int data[maxn];
	int ans=-(1<<30),s,t,temp;
	int doo(){
		freopen("subq.in","r",stdin);
		freopen("subq.out","w",stdout);
		int n;scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&data[i]),data[i]+=data[i-1];
		deque<int>q;
		for(int i=1;i<=n;i++){
			while( !q.empty() && data[q.back()]>=data[i-1]) q.pop_back();
			q.push_back(i-1);
			temp=q.front();
			if(ans < data[i]-data[temp]){
				ans=data[i]-data[temp];
				s=temp+1;t=i;
			}
		}
		printf("%d\n%d\n%d\n",s,t,ans);
		return 0;
	}
}
int aaa = cat::doo();
int main(){;}