看了下数据范围，需要在O(n)下解决，区间和一眼维护前缀和做差即可，现在要求最大序列和，对于每一位前缀和，维护一下本身与其右边所有数的最小值，该位的前缀和与该其左侧的最小值的差值就是以该位为终点的前缀和最大值，遍历一遍整个前缀和序列，找到全部范围的最大值就行。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
#define maxn 1000000+10
#define inf 0x3f3f3f3f
#define ll long long

ll n;
ll sa[maxn];
ll minn[maxn];
int main() {
//	freopen("1.txt","r",stdin); 
	while(cin>>n){
		ll cnt;
		memset(minn,127,sizeof(minn));
		minn[0]=0;
		for(int i=1;i<=n;i++){
			cin>>cnt;
			sa[i]=sa[i-1]+cnt;
		//	cout<<minn[i-1]<<" ";
			if(sa[i]<minn[i-1]){
				minn[i]=sa[i];
			}
			else 
				minn[i]=minn[i-1];
	//		cout<<sa[i]<<" ";
		}
		ll maxx=-0x7FFFFFFFFFFFFFFF;
		for(int i=1;i<=n;i++){
			maxx=max(sa[i]-minn[i-1],maxx);
		//	cout<<sa[i]-minn[i-1]<<" ";
		}
		cout<<maxx<<endl;
	}
	return 0;
}