POJ-2593 Max Sequence（不连续的最大子段和）

Max Sequence

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 16001		Accepted: 6715

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 20
0

Sample Output

40

大致题意：给出一个数列，求出数列中不相交的两个子段和，要求子段和最大。

 1 #include <stdio.h>
 2 int main()
 3 {
 4     int left[100005];
 5     int right[100005];
 6     int a[100005];
 7     while(1)
 8     {
 9         int n,i;
10         scanf("%d",&n);
11         if(n==0)
12             break;
13         for(i=0;i<n;i++)
14             scanf("%d",&a[i]);
15         int sumL=0;
16         int max=-99999999;
17         for(i=0;i<n;i++)//从左向右求到i结尾的最大连续子串的最大值    //如果这个循环看不懂的话，可以先做下hdu1003
18         {
19             sumL=sumL+a[i];
20             if(sumL>max)
21                 max=sumL;
22             if(sumL<0)
23                 sumL=0;
24             left[i]=max;
25         }
26         max=-99999999;
27         int tmp=-99999999;
28         int sumR=0;
29         for(i=n-1;i>=1;i--)
30         {
31             sumR=sumR+a[i];
32             if(sumR>max)
33                 max=sumR;
34             if(sumR<0)
35                 sumR=0;
36             if(tmp<max+left[i-1])
37             tmp=max+left[i-1];
38          }
39          printf("%d
",tmp);
40      }
41      return 0;
42 }