poj-2593 Max Sequence

Max Sequence

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 14335		Accepted: 6012

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

Source

POJ Monthly--2005.08.28,Li Haoyuan

题意：求一个序列中两个不相交的连续子段的最大和

 1  /*代码一：  -----TLE
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 int num[100001], dp[2][100001];
 9 //dp[i][j] 表示 前 j 项中选择 i 个连续子段所得的最大和，且第 i 个连续子段是以 num[j]结尾的 
10 int main()
11 {
12     int n;
13     while(scanf("%d", &n), n)
14     {
15         memset(dp, 0, sizeof(dp));
16         for(int i = 1; i <= n; ++i)
17         {
18             scanf("%d", &num[i]);
19             dp[1][i] = num[i];
20         }
21         for(int j = 1; j <= 2; ++j)
22         {
23             for(int i = 1; i <= n; ++i)
24             {
25                 for(int t = 1; t < i-1; ++t)
26                     dp[j][i] = max(dp[j][i-1], dp[j-1][t]) + num[i];
27             }
28         }
29         printf("%d
", dp[2][n]);
30     }
31     return 0;
32 }
33 */
34 //代码二：--------AC 
35 #include <cstdio>
36 #include <iostream>
37 #include <cstring>
38 
39 using namespace std;
40 
41 int num[100001], dp[100001];
42 // dp[i] 存储前 i 项的最大字段和 
43 int main()
44 {
45     int n, max, sum, ans;
46     while(scanf("%d", &n), n)
47     {
48         sum = 0;
49         max = -0x3fffffff;
50         //memset(dp, 0, sizeof(dp));
51         for(int i = 1; i <= n; ++i)
52         {
53             scanf("%d", &num[i]);
54             sum += num[i];
55             if(sum > max)
56                 max = sum;
57             dp[i] = max;
58             if(sum < 0)
59                 sum = 0;
60         }
61         dp[0] = ans = max = -0x3fffffff;
62         sum = 0;
63         for(int i = n; i > 0; --i) // 逆向遍历 
64         {
65             sum += num[i];
66             if(sum > max)
67                 max = sum;
68             if(ans < max+dp[i-1])
69                 ans = max+dp[i-1];
70             if(sum < 0)
71                 sum = 0;
72         }
73         printf("%d
", ans);
74     }
75     return 0;
76 }