pku2479.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 52 行

int main()
{
	int T, N, i, nfrom, max, temp;
	int left[60000], right[60000],num[60000];
	scanf("%d",&T);
	
	while(T--)
	{
		scanf("%d",&N);
		
		for(i=0;i<N;i++)
		{
			scanf("%d",num+i);	
		}
		
		nfrom=num[0];
		left[0]=num[0];
		for(i=1;i<N;i++)
		{
			if(nfrom < 0) nfrom = num[i];
			else nfrom=nfrom+num[i];
			
			if(nfrom > left[i-1]) left[i]=nfrom;
			else left[i]=left[i-1];
		}	

		nfrom=num[N-1];
		right[N-1]=num[N-1];
		for(i=N-2;i>=0;i--)
		{
			if(nfrom < 0) nfrom = num[i];
			else nfrom=nfrom+num[i];
			
			if(nfrom > right[i+1]) right[i]=nfrom;
			else right[i]=right[i+1];
		}	

		max=left[0]+right[1];
		
		for(i=1;i<N-1;i++)
		{
			temp=left[i]+right[i+1];
			if(temp>max)
				max=temp;
		}
		printf("%d\n",max);
	}
	return 0;
}