#include <iostream>
using namespace std;

int s[50000];
int mss(int l,int r){
	int i,j;
	int max = s[l];
//	int imax = l;
	for(i=l;i<=r;i++){
		if(s[i]>max){ //找到从l到i的最大值
			max=s[i];
//			imax = i;
		}
		if(max>0) //如果某次max>0 也就是找到了第一个正数 那么break出来，而且这个正数必为s[i]
			break;	
	}
	if(i==r+1) //如果遍历完整个l到r，则证明从来没有正数的存在 那么 最大和就是最大的那个正数
		return max;
	//如果存在正数s[i] 那么必在i处break出来 我们就要从i处开始游标法

	int maxsum = s[i];
	int sum = s[i];
	for(j=i+1;j<=r;j++){
		sum+=s[j];
		if(sum>maxsum)
			maxsum = sum;
		if(sum <= 0){
			i = j+1;
			sum = 0;
		}
	}
	return maxsum;
}
int main(int argc, char* argv[])
{
	int T,n;
	int i;
	cin >> T;
	while(T--){
		int ans =0;
		int maxans;
		cin >> n;
		for(i=0;i<n;i++)
			scanf("%d",&s[i]);
			//			cin >> s[i];
		maxans = mss(0,0)+mss(1,n-1);
//		cout << maxans << endl;
		for(i=1;i<n-1;i++){
			ans = mss(0,i)+mss(i+1,n-1);
			if (ans>maxans)
				maxans = ans;
//			cout << ans<< " "<< mss(0,i)<<" "<< mss(i,n-1)<<  endl;
		}
		cout << maxans << endl;
	}
	system("pause");
	return 0;
}

• 这个做两遍O（N）的DP，2遍O（N）更新，然后O（N）扫描一遍 (0) lqp18_31 2009-08-07 16:51:07
  • Re:这个做两遍O（N）的DP，2遍O（N）更新，然后O（N）扫描一遍 (14) kakassi 2009-08-07 20:42:57
• 自习看了网上搜到的思路 折服了 折服了 (1190) kakassi 2009-08-08 12:30:06
  • Re:仔细看了网上搜到的思路 折服了 折服了 (0) kakassi 2009-08-08 12:30:24