#include<bits/stdc++.h>
using namespace std;
int a[200010],f[200010],i,j,le,mx,n,r=1,sumn;
bool fg;
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		f[i]=f[i-1]+a[i];//前缀和
		if(f[i]>=f[r])//求从1开始的最大子段和
			r=i;
		if(a[i]>0)
			fg=true;//fg代表是否有正数
	}
	if(!fg)//没有正数
	{
		mx=-10001;
		for(i=1;i<=n;++i)
			mx=max(mx,a[i]);
		printf("%d",mx);//求最大的一个数即为答案
	}
	else//有正数
	{
		le=1;//le代表左端点，r代表右端点
		mx=sumn=f[r];
		while(r<=n)//右端点不出界
		{
			for(;le<=r;++le)
			{
				sumn-=a[le-1];//减去上一个 
				if(sumn>mx)
					mx=sumn;
			}
			for(i=++r;i<=n;++i)
			{
				if(f[i]-f[le-1]>=f[r]-f[le-1])
					r=i;
			}
			sumn=f[r]-f[le-2];//由于新一轮循环会重复减去a[le-1]，所以在这里少减去一个
		}
		printf("%d",mx);//最大子段和
	}
	return 0;
}

结果，悬赏关注