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 { 5int input[LEN]; 6int left[LEN]; 7int right[LEN]; leftMax[LEN];10int rightMax[LEN];max = -500000000; cases;15int n;, &cases);(cases–)19 {, &n);21if(n < 2)22break;23int i;24for(i = 0; i < n; i++)25 {, &input[i]);27if(i == 0)28 {29left[0] = input[0];30leftMax[0] = left[0];31if(leftMax[0] > max)32max = leftMax[0];33 }{36if(left[i – 1] < 0)37 {38left[i] = input[i];39if(left[i] > max)40max = left[i];41leftMax[i] = max;42 }{45left[i] = input[i] + left[i-1];46if(left[i] > max)47max = left[i];48leftMax[i] = max;49 }50 }51 }52max = -500000000;53for(i = n – 1; i >=0; i–)54 {55if(i == n – 1)56 {57right[i] = input[n-1];58rightMax[i] = right[i];59if(rightMax[i] > max)60max = rightMax[i];61 }{64if(right[i + 1] < 0 )65 {66right[i] = input[i];67if(right[i] > max)68max = right[i];69rightMax[i] = max;70 }{73right[i] = input[i] + right[i + 1];74if(right[i] > max)75max = right[i];76rightMax[i] = max;77 }78 }79 }80max = -500000000;(n == 2)83max = input[0] + input[1];{86for(i = 0; i < n – 1; i++)87 {88if((leftMax[i] + rightMax[i+1]) > max)89max = leftMax[i] + rightMax[i+1];90 }91 }, max);94max = -500000000;95 };97 }
posted on
午餐，晚餐。或许吃得不好，可是却依旧为对方擦去嘴角的油渍。
