2230612_ac_187ms_620k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

long num[100001], l[100001], r[100001];

void input()
{
	int T;
	long i, n;
	long sum, t, max;

	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i = 0; i < n; i++)
			scanf("%d",&num[i]);
		sum = 0; t = num[0];
		for(i = 0; i < n; i++)
		{
			if(sum<0)
				sum = num[i];
			else
				sum += num[i];
			if(t<sum)
				t = sum;
			l[i] = t;
		}
		sum = 0; t = num[n-1];
		for(i = n-1; i >= 0; i--)
		{
			if(sum<0)
				sum = num[i];
			else
				sum += num[i];
			if(t<sum)
				t = sum;
			r[i] = t;
		}
		max = l[0]+r[1];
		for(i = 1; i < n-1; i++)
			if(l[i]+r[i+1]>max)
				max = l[i]+r[i+1];
		printf("%ld\n",max);
	}
}

int main()
{
	input();
	return 1;
}