> #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;
> }
> 

• Re:仔细看了网上搜到的思路 折服了 折服了 (0) kakassi 2009-08-08 12:30:24