/*
	name: Maximum sum
	author: Y_zou
	time: 2005_8_21	
*/

#include <iostream>
#include <cstdio>

using namespace std;
int arrayB[50001];
int arrayC[50001];

int MaxSum(int cnt,int* buff)
{
	if(cnt<2)
		return 0;
	
	arrayB[0] = 0;
	arrayC[1] = 0;
	for(int i=1;i <= 2; i++)
	{
		arrayB[i] = arrayB[i-1] + buff[i];
		arrayC[i-1] = arrayB[i];
		int max = arrayB[i];
		for(int j=i+1; j<=i+cnt-2; j++)
		{
			arrayB[j] = arrayB[j-1] > arrayC[j-1] ? arrayB[j-1]+ buff[j] : arrayC[j-1] + buff[j];
			arrayC[j-1] = max;
			if(max < arrayB[j])
				max = arrayB[j];
		}
		arrayC[i+cnt-2] = max;
	}
	int sum = 0;
	for(int c=2; c<=cnt; c++)
	{
		if(sum < arrayB[c])
			sum = arrayB[c];
	}
	return sum;


}
int main()
{
	int Case,cnt;
	int i;
	int buff[50001];

	scanf("%d",&Case);
	for(int c=0; c <Case; c++)
	{
		if(c)
			cout << endl;
		scanf("%d", &cnt);
		for(i=1; i <= cnt; i++)
		{
			scanf("%d",&buff[i]);
		}
		int sum = 0;

		if(cnt==2)
		{
			sum =  buff[1] + buff[2];
			if(sum > buff[1] && sum > buff[2])
				cout << sum << endl;
			else
			{
				if(buff[1] > buff[2])
					cout << buff[1] << endl;
				else
					cout << buff[2] << endl;
			}
		}
		else
	 		cout << MaxSum(cnt, buff) << endl;
	}

	return 0;
}

• Re:我用的是最大子段和　ＤＰ　还是ＷＡ　不知道错哪里了 (1499) acme 2005-09-18 15:20:52