问题：求一个数组 / 序列的满足条件的子数组 / 子序列。
条件： 1. 子数组必须是连续的。 2. 求和即可，不需要返回子数组是哪段。 3. 数组元素为整数。
例子：
1. [1,-2,3,5,-3,2] 应该返回 8 。
2. [0,-2,3,5,-1,2] 应该返回 9 。
3. [-9,-2,-3,-5,-3] 应该返回 -2 。也就是说全部为负数的话，返回最小的负数。
这是《编程之美》上的一道题，比较充分的体现了算法改进的思路。
解法一：
最直接的解法当然是穷举遍历了，把所有的子数组列出来，然后计算和。
复杂度可以简单的想出来：设置两个变量 i 和 j 为子数组边界，这两个变量都要遍历整个数组，然后还需要一个游标 k ，来遍历整个子数组以求和。所以总的复杂度是 O （ n^3 ）。
代码如下：
1 int MaxSubSum( int * A, int n) 2 { 3 int max = - INFINITE; 4 int sum = 0 ; 5 for ( int i = 0 ; i < n ; i ++ ) 6 { 7 for ( int j = i ; j < n ; j ++ ) 8 { 9 for ( int k = i ; k <= j ; k ++ ) 10 { 11 sum += A[k]; 12 } 13 if (sum > max) 14 { 15 max = sum; 16 } 17 } 18 } 19 return max; 20 } 21解法一改进版：
仔细琢磨就会发现，其实不需要再使用 k 去遍历子数组，因为每次 j 移动都会产生新的子数组，所以只要在每次 j 移动时进行一下比较，就不会把最大值漏掉。所以只有 i 和 j 移动，复杂度降低到 O （ n^2 ）。
代码如下：
1 int MaxSubSum( int * A, int n) 2 { 3 int max = - INFINITE; 4 int sum = 0 ; 5 for ( int i = 0 ; i < n ; i ++ ) 6 { 7 sum = 0 ; 8 for ( int j = i ; j < n ; j ++ ) 9 { 10 sum += A[j]; 11 if (sum > max) 12 max = sum; 13 } 14 } 15 return max; 16 } 17解法二 ：分治算法
跟二分查找的思想相似，我们可以分情况讨论这个问题是不是符合二分查找的条件。
情况 1. 这个满足最大和的子数组全部在本数组的左半部或者右半部。例如：左半部 A[i]……A[n/2-1] 或者右半部 A[n/2]……A[j] 。这种情况下可以直接使用递归调用。
情况 2. 满足最大和的子数组跨过了本数组的中间点。例如： A[i]……A[n/2-1] A[n/2]……A[j] 连续。则这种情况下只要在左半部寻找以 A[n/2-1] 结尾，在右半部寻找以 A[n/2] 开头的两个满足最大和的连续数组，并求和即可。由于这个已知起点，只需要一个游标即可，所以复杂度是 2*O （ n/2 ） =O （ n ）。
综合以上两种情况，满足分治算法递归式： T （ n ） =2T （ n/2 ） +O （ n ） =O （ n*logn ）。
代码如下：
1 int MaxSubSum( int * A, int Left, int Right) 2 { 3 // 4 int MaxLeftSum,MaxRightSum; 5 // 左右子数组的和的最大值 6 int MaxLeftPartSum,MaxRightPartSum; 7 // 临时变量，用于存储计算出来的和 8 int LeftPartSum,RightPartSum; 9 int Center,i; 10 11 // 其中某一部分只有一个元素 12 if (Left == Right) 13 { 14 if (A[Left] > 0 ) 15 return A[Left]; 16 else 17 return 0 ; 18 } 19 20 // 递归调用。分别计算左右子数组的最大和子数组。 21 // 即假设最大和子数组没有被Center切割 22 Center = (Left + Right) / 2 ; 23 MaxLeftSum = MaxSubSum(A,Left,Center); 24 MaxRightSum = MaxSubSum(A,Center + 1 ,Right); 25 26 // 假设最大和子数组被Center切开的情况 27 // 那么需要从Center开始向两侧计算 28 MaxLeftPartSum = 0 ; 29 LeftPartSum = 0 ; 30 for (i = Center ; i >= Left; -- i ) 31 { 32 LeftPartSum += A[i]; 33 if (LeftPartSum > MaxLeftPartSum) 34 MaxLeftPartSum = LeftPartSum; 35 } 36 MaxRightPartSum = 0 ; 37 RightPartSum = 0 ; 38 for (i = Center + 1 ; i <= Right ; ++ i) 39 { 40 RightPartSum += A[i]; 41 if (RightPartSum > MaxRightPartSum) 42 MaxRightPartSum = RightPartSum; 43 } 44 // 返回三者中的最大值。 45 return max(max(MaxLeftSum,MaxRightSum),MaxLeftPartSum + MaxRightPartSum); 46 } 47解法三：
我们试着再观察这个数组的特点，一个元素一个元素的看。
根据 A[0] 是否在这个满足最大和的子数组中，我们可以分为两种情况。
1. 在。那么可以从 A[0] 开始求（比较容易）。
2. 不在。那么这种情况，又可以继续分为两种情况： A[1] 在不在这个满足最大和的子数组中。
从这里我们可以观察出一种递归的特点，可以把一个规模为 N 的问题转化为规模为 N-1 的问题。所以这个从 A[0] 到 A[n-1] 的最大和子数组问题分解成：
1. 所求子数组中包含 A[0] 。如果不包含 A[1] ，则 A[0] 自己满足条件，此时 Max （ A[0]……A[n-1] ） =A[0] 。如果包含 A[1] ，则 Max （ A[0]……A[n-1] ） =A[0]+Max （ A[1]……A[n-1] ）。
2. 所求子数组中不包含 A[0] 。 Max （ A[0]……A[n-1] ） =Max （ A[1]……A[n-1] ）。
最终结果取以上三者的最大值即可，即 Max （ A[0]……A[n-1] ） =max （ A[0], A[0]+Max （ A[1]……A[n-1] ） , Max （ A[1]……A[n-1] ） ）。
这个的复杂度为线性：因为只要把数组遍历一遍即可。
代码如下：
1 int MaxSubSum( int * A, int n) 2 { 3 // 假设满足最大和的子数组就是从StartFrom[i]开始 4 int * StartFrom = new int [n]; 5 memset(StartFrom,n, 0 ); 6 StartFrom[n - 1 ] = A[n - 1 ]; 7 // 假设A[i]之后满足最大和的子数组的和为Longest[i]（不一定包括A[i]） 8 int * Longest = new int [n]; 9 memset(Longest,n, 0 ); 10 Longest[n - 1 ] = A[n - 1 ]; 11 12 for ( int i = n - 2 ; i >= 0 ; i -- ) 13 { 14 // 如果从i开始，那么要么最大和只包括A[i]自己，要么就是后面的那个序列连上A[i] 15 StartFrom[i] = max(A[i],A[i] + StartFrom[i + 1 ]); 16 // 最大和，要么是从i开始的，要么还是以前的 17 Longest[i] = max(StartFrom[i],Longest[i + 1 ]); 18 } 19 // 最后结果是在号元素中保存 20 return Longest[ 0 ]; 21 } 22由于这种前后单元素的相关性，实际上不需要两个数组来储存这个信息，只需要两个变量即可，这样可以减小程序的空间复杂度。
代码如下：
1 int MaxSubSum( int * A, int n) 2 { 3 // 假设满足最大和的子数组就是从StartFrom开始 4 int StartFrom = A[n - 1 ]; 5 // 假设A[i]之后满足最大和的子数组的和为Longest（不一定包括A[i]） 6 int Longest = A[n - 1 ]; 7 8 for ( int i = n - 2 ; i >= 0 ; i -- ) 9 { 10 // 如果从i开始，那么要么最大和只包括A[i]自己，要么就是后面的那个序列连上A[i] 11 StartFrom = max(A[i],A[i] + StartFrom); 12 // 最大和，要么是从i开始的，要么还是以前的 13 Longest = max(StartFrom,Longest); 14 } 15 // 最后结果是在0号元素中保存 16 return Longest; 17 } 18