文章来源：http://hi.baidu.com/macrofuns/item/21fc130ed6570adf72e67643
问题描述：
有n个数（以下都视为整数），每个数有正有负，现在要在n个数中选取相邻的一段，使其和最大，输出最大的和。
问题分析：
看到这个问题，它是属于带“最”字的问题，其实就是一个求最优解的问题。对于这种问题的朴素算法就是枚举出每种可能，然后在其中寻找一个最优的解，然后输出。因为输出仅要求这个子段的和，因此不必再记录关于解的组成的信息。
朴素算法是用i和j表示序列i到j的子段，然后判断这个子段的和是否是最大的，是就记录。然后用k求i到j之间的和，因此是O(n^3)的算法。
1 int LSS_SlowEnumerate(int a[]) //最大子段和，枚举算法，O(n^3) 2 { 3 int max = 0, n = a[0], sum; 4 5 for (int i = 1; i <= n; i++) 6 { 7 for (int j = 1; j <= n; j++) 8 { 9 sum = 0; //sum 为区间 [i, j] 之间的最大和 10 for (int k = i; k <= j; k++) 11 { 12 sum += a[k]; 13 } 14 15 if (sum > max) 16 max = sum; 17 } 18 } 19 20 return max; 21 }
看了这个算法，我们不禁会想，有没有能更快的算法呢？毕竟O(n^3)的时间效率是很低的。答案肯定是有的，我们可以令一个数组sum，sum[i]代表 了序列从1到i的和。如果要算i到j的和，只需将sum[j]减去sum[i-1]即可，这无疑可以去掉最里层的循环，从而直接调用和的信息，时间效率提 高到O(n^2)。
1 int LSS_Enumerate(int a[]) //最大子段和，枚举算法，O(n^2) 2 { 3 int sum[101], i, n = a[0], max = -200000000, t; //sum[i] 表示 a[i] 的前 i 项和 4 5 sum[0] = 0; 6 7 for (i = 1; i <= n; i++) 8 { 9 sum[i] = sum[i - 1] + a[i]; 10 } 11 12 for (i = 0; i <= n - 1; i++) //枚举每个可能的子段 13 { 14 for (int j = i + 1; j <= n; j++) 15 { 16 t = sum[j] - sum[i]; 17 if (t > max) 18 max = t; 19 } 20 } 21 22 return max; 23 }
上面两种算法都是朴素算法，枚举每个可能，从而找到最优的解。然而还有没有更优的解呢？答案依旧是肯定的。
我们不妨从小规模数据分析，当序列只有一个元素的时候，最大的和只有一个个可能，就是选取本身；当序列有两个元素的时候，只有三种可能，选取左边元素、选 取右边元素、两个都选，这三个可能中选取一个最大的就是当前情况的最优解；对于多个元素的时候，最大的和也有三个情况，从左区间中产生、从右区间产生、左 右区间各选取一段。因此不难看出，这个算法是基于分治思想的，每次二分序列，直到序列只有一个元素或者两个元素。当只有一个元素的时候就返回自身的值，有 两个的时候返回3个中最大的，有多个元素的时候返回左、右、中间的最大值。因为是基于二分的思想，所以时间效率能达到O(nlgn)。
1 int LSS_Recursion(int a[], int l, int r) //最大子段和，分治算法，O(nlgn) 2 { 3 int m = (l + r) / 2, t = 0, L = 0, R = 0; //L为左区间能取到的最大，R为右区间能取到的最大 4 5 if (l == r) //边际条件：当区间元素只有一个的时候返回自身 6 return a[m]; 7 8 if (r - l == 1) //边际条件：当区间元素只有两个的时候返回左、右、左右相加三者中的最大值 9 return Max(Max(a[l], a[r]), a[l] + a[r]); 10 11 int LMax = LSS_Recursion(a, l, m); //递归左区间 12 int RMax = LSS_Recursion(a, m + 1, r); //递归右区间 13 14 for (int i = m; i >= 1; i--) //左边找一个最大的和 15 { 16 t += a[i]; 17 if (t > L) 18 L = t; 19 } 20 21 t = 0; 22 23 for (int i = m + 1; i <= r; i++) //右边找一个最大的和 24 { 25 t += a[i]; 26 if (t > R) 27 R = t; 28 } 29 30 return Max(Max(LMax, RMax), L + R); //返回左区间的和、右区间的和、两者连起来的和中最大的 31 }
有了O(nlgn)的递归算法，那还能找到O(n)线性时间的算法么？——动态规划。我们令一个数组f，f[i]表示前i个元素能组成的最大和。如果 f[i-1]大于零，则不管a[i]的情况，f[i-1]都可以向正方向影响a[i]，因此可以将a[i]加在f[i-1]上。如果f[i-1]小于零， 则不管a[i]再大，都会产生负影响，因此我们还不如直接令f[i]=a[i]。因此状态转移方程就在这里。我们只需在f中扫描一次，找到最大的值就是最 大子段的和。
1 int LSS_DP(int a[]) //求最大子段和，动态规划，O(n) 2 { 3 int f[101], n = a[0], max = -200000000; //f[i]表示第 i 个数能构成的最大和， max 表示当前所有中的最大和 4 5 f[1] = a[1]; 6 7 for (int i = 2; i <= n; i++) 8 { 9 if (f[i - 1] > 0) //如果第 i 个数后面一个数能构成的最大子段和大于 0 10 { 11 f[i] = f[i - 1] + a[i]; //大于就将第 i 个数加入其中 12 } 13 else 14 f[i] = a[i]; //否则第 i 个数自己组成一个最大子序列 15 16 if (f[i] > max) //更新最大值 17 max = f[i]; 18 } 19 20 return max; 21 }
以上四个算法，从3个不同的思想解决了最大子段和问题，不管从时间效率还是代码量来说，动态规划都是最优的，仅需要一个辅助数组f来临时存取，因此时间复杂度空间复杂度都是线性的。
转载声明：版权归原作者所有，转载请注明来源：http://hi.baidu.com/macrofuns/item/21fc130ed6570adf72e67643
