转载请注明出处：

viewmode=contents

题目链接：

----------------------------------------------------------------------------------------------------------------------------------------------------------

欢迎光临天资小屋：

----------------------------------------------------------------------------------------------------------------------------------------------------------

Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N). 

You should output S. 

Input

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5-5 9 -5 11 200

Sample Output

40

 思想：

对于数据a[]，从左向右依次求解以a[i]结尾的最大子段和b[i]，

  然后，从右向左遍历，求a[i]右边（包含a[i]）的最大子段和sum，输出sum+b[i-1]的  最大值。

代码例如以下：

#include 
     
      using namespace std;#define INF 0x3fffffff#define M 100000+17int a[M],b[M];int main(){	int n,i;	while(cin >> n && n)	{		int sum = 0, MAX = -INF;		for(i = 1; i <= n; i++)		{			cin >> a[i];			sum+=a[i];			if(sum > MAX)			{				MAX = sum;			}			b[i] = MAX;			if(sum < 0)			{				sum = 0;			}		}		MAX = -INF;		sum = 0;		int ans = MAX, t;		for(i = n; i > 1; i--)		{			sum+=a[i];			if(sum > MAX)			{				MAX = sum;			}			t = MAX + b[i-1];			if(t > ans)			{				ans = t;			}			if(sum < 0)			{				sum = 0;			}		}		cout<
      
       <
      
     

版权声明：本文博客原创文章。博客，未经同意，不得转载。