，题目大意是：对于给定的整数序列A={a1, a2,..., an}，我们如下定义函数 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 #include2 #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 else35 {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 else44 {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 else63 {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 else72 {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 else85 {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 }