POJ 2479 Maximum sum (动态规划)

POJ 2479 Maximum sum，题目大意是：对于给定的整数序列A={a1, a2,..., an}，我们如下定义函数 d(A)：

我们的目标就是求出d(A)

解决方案：
这个题目是一个典型的动态规划题目，我们可以这样看，d(A)最大，即两个子序列之和最大，而这两个子序列是不相交的，因而我们可以将题目转换为如下形式：
第一步，对于位置i，求i左边序列(可以包含i)的最大值和i右边序列的最大值。在程序中分别用leftMax和rightMax数组进行保存。
第二步，然后对i取不同的值，即遍历i，得到d(A)。

如对于序列A = {1 -1 2 2 3 -3 4 -4 5 -5}，我们对于A[0]，求其左边序列(就是它自己)的最大值和它右边序列的最大值，然后相加，保存相应的值d。
然后对于A[1]，求其左边序列的最大值和右边序列的最大值，然后相加，和上次计算的出来的d比较，若大，则保存之，若小，则废弃之。
......
依次循环下去

在上述过程中，我们还会总结出一个规律，当我们遍历 i 来计算leftMax时，需要一个数组left来保存“包含input[i]的连续序列的和的最大值”，这个解释一下，如序列 input = {1,1,-6,-3,5,4}，当 i 为3，即扫描到input[3] = -3时，这时我们来求left[3]，我们发现包含input[3]的连续序列的和的最大值为-3，即这个序列就是其自己。而对于left[2]来说，left[2] = -4，即这个序列为{1,1,-6}。

我们就用input = {1,1,-6,-3,5,4}来扫描一遍，

i = 0，input[0] = 1，left[0] = 1，leftMax[0] = 1；

i = 1，input[1] = 1，left[1] = 1 + 1 = 2，leftMax[1] = 2；

i = 2，input[2] = -6，left[2] = 1 + 1 + -6 = -4，leftMax[2] = 2；

i = 3，input[3] = -3，left[3] = -3，leftMax[3] = 2；

i = 4，input[4] = 5，left[4] = 5，leftMax[4] = 5；

i = 5，input[5] = 4，left[5] = 9，leftMax[5] = 9；

结合代码走一遍就会明白整个过程了。

代码如下：

 1 #include <stdio.h>  
 2 #define LEN 50000
 3 int main()
 4 {
 5     int input[LEN];
 6     int left[LEN];
 7     int right[LEN];
 8 
 9     int leftMax[LEN];
10     int rightMax[LEN];
11 
12     int max = -500000000;
13 
14     int cases;
15     int n;
16     scanf("%d", &cases);
17 
18     while(cases--)
19     {
20         scanf("%d", &n);
21         if(n < 2)
22             break;
23         int i;
24         for(i = 0; i < n; i++)
25         {
26             scanf("%d", &input[i]);
27             if(i == 0)
28             {
29                 left[0] = input[0];
30                 leftMax[0] = left[0];
31                 if(leftMax[0] > max)
32                     max = leftMax[0];
33             }
34             else
35             {
36                 if(left[i - 1] < 0)
37                 {
38                     left[i] = input[i];
39                     if(left[i] > max)
40                         max = left[i];
41                     leftMax[i] = max;
42                 }
43                 else
44                 {
45                     left[i]  = input[i] + left[i-1];
46                     if(left[i] > max)
47                         max = left[i];
48                     leftMax[i] = max;
49                 }
50             }
51         }
52         max = -500000000;
53         for(i = n - 1; i >=0; i--)
54         {
55             if(i == n - 1)
56             {
57                 right[i] = input[n-1];
58                 rightMax[i] = right[i];
59                 if(rightMax[i] > max)
60                     max = rightMax[i];
61             }
62             else
63             {
64                 if(right[i + 1] < 0 )
65                 {
66                     right[i] = input[i];
67                     if(right[i] > max)
68                         max = right[i];
69                     rightMax[i] = max;
70                 }
71                 else
72                 {
73                     right[i] = input[i] + right[i + 1];
74                     if(right[i] > max)
75                         max = right[i];
76                     rightMax[i] = max;
77                 }
78             }
79         }
80         max = -500000000;
81 
82         if(n == 2)
83             max = input[0] + input[1];
84         else
85         {
86             for(i = 0; i < n - 1; i++)
87             {
88                 if((leftMax[i] + rightMax[i+1]) > max)
89                     max = leftMax[i] + rightMax[i+1];
90             }
91         }
92 
93         printf("%d\n", max);
94         max = -500000000;
95     }
96     return 0;
97 }