#include <stdio.h>
#include <iostream>

using namespace std;

int main()
{
	static int cases,Arraynum,Array[10000];
	int i,j,k,Flag;
	static int mark,MaxL[10000],MaxR[10000],ans,neg;
	cin>>cases;
	while(cases==0)
	{
		cin>>Arraynum;
		for(i=0;i<Arraynum;i++)
			cin>>Array[i];
		for(mark=0;mark<Arraynum;mark++)  //该数字前后的子数组最大值
		{
			for(i=Flag=neg=0;i<=mark;i++)           //包含mark
			{
				if(Array[i]>0&&Flag==0) 
				{
					Flag=1;
					MaxL[mark]+=Array[i];
					continue;
				}
				if(Array[i]>0&&Flag==1)
				{
					if(neg+Array[i]>=0) 
					{
						MaxL[mark]+=(neg+Array[i]);
						neg=0;
					}
					continue;
				}
				if(Array[i]<=0&&Flag==1) neg+=Array[i];
			}
			for(j=Arraynum-1,Flag=neg=0;j>mark;j--)      //不包含mark
			{
				if(Array[j]>0&&Flag==0) 
				{
					Flag=1;
					MaxR[mark]+=Array[j];
					continue;
				}
				if(Array[j]>0&&Flag==1)
				{
					if(neg+Array[j]>=0) 
					{
						MaxR[mark]+=(neg+Array[j]);
						neg=0;
					}
					continue;
				}
				if(Array[j]<=0&&Flag==1) neg+=Array[j];
			}
		}
		for(mark=0;mark<Arraynum;mark++) 
			if(MaxL[mark]+MaxR[mark]>ans)  ans=MaxL[mark]+MaxR[mark];
		printf("%d\n",ans);
	}
	return 0;
}

• Re:大神指点下为什么这个代码会超过时间限制 (1372) harrymew 2012-05-23 02:07:00