寻找数组A的和最大的非空连续子数组。例如：A[] = {1, -2, 3, 10, -4, 7, 2, -5}的最大子数组为3, 10, -4, 7, 2，其最大和为18。数组元素都为负时，返回最大负值。

解法一：暴力枚举，O(N^2)

1 //left,最大子数组左端 2 //right,最大子数组右端 3 //n数组arr元素个数 4 const int IntMin = (signed int)0x80000000; 5 int MaxSum(int *arr, int &left, int &right, int n) 6 { 7     if (!arr || n <= 0) { 8         left = -1; 9         right = -1;10         return IntMin;11     }12 13     int maxSum = IntMin;14     for (int i = 0; i < n; ++i) {15         int sum = 0;16         for (int j = i; j < n; ++j) {17             sum += arr[j];18             if (sum > maxSum) {19                 left = i;20                 right = j;21                 maxSum = sum;22             }23         }24     }25     return maxSum;26 }

解法二：分治，O(NlogN)

寻找数组A[low…high]的最大子数组时，将数组划分为两个规模尽可能相等的子数组 A[low…mid]和A[mid+1…high]。

A[low…high]的任何连续子数组A[i…j]所处的位置必然是三种情况之一：

（1）完全位于子数组A[low..mid]中，因此low<=i<=j<=mid; 

（2）完全位于子数组A[mid + 1..high]中，因此mid<=i<=j<=high;

（3）跨越了中点，因此low<=i<=mid<j<=high;

A[low…high]的一个最大子数组必然是完全位于A[low…mid]中、完全位于A[mid+1…high]中或者跨越中点的所有子数组中和最大者。

1 //left和right是返回值,未初始化,不能直接使用 2 const int IntMin = (signed int)0x80000000; 3 int MaxSumCross(int *arr, int &left, int mid, int &right, int n) 4 { 5     if (arr == NULL) { 6         left = -1; 7         right = -1; 8         return IntMin; 9     }10 11     int lmaxSum = IntMin;12     int sum = 0;13     for (int i = mid; i >= 0; --i) {14         sum += arr[i];15         if (sum > lmaxSum) {16             left = i;17             lmaxSum = sum;18         }19     }20 21     int rmaxSum = IntMin;22     sum = 0;23     for (int i = mid + 1; i < n; ++i) {24         sum += arr[i];25         if (sum > rmaxSum) {26             right = i;27             rmaxSum = sum;28         }29     }30     return lmaxSum + rmaxSum;31 }32 33 int MaxSum(int *arr, int &left, int &right, int n)34 {35     if (!arr || left > right || n <= 0) {36         left = -1;37         right = -1;38         return IntMin;39     }40     if (left == right) 41         return arr[left];42 43     //lleft,lright左子数组的左端,右端44     //rleft,rright右子数组的左端,右端45     //mleft,mright中间子数组的左端,右端46     int mid = left + (right - left) / 2;47     int lleft = left, lright = mid;48     int rleft = mid + 1, rright = right;49     int mleft, mright;50     int leftSum = MaxSum(arr, lleft, lright, n);51     int midSum = MaxSumCross(arr, mleft, mid, mright, n);52     int rightSum = MaxSum(arr, rleft, rright, n);53 54     if (leftSum >= rightSum && leftSum >= midSum) {55         left = lleft;56         right = lright;57         return leftSum;58     } else if (rightSum >= leftSum && rightSum >= midSum) {59         left = rleft;60         right = rright;61         return rightSum;62     } else if (midSum >= leftSum && midSum >= rightSum) {63         left = mleft;64         right = mright;65         return midSum;66     }67 }

解法三：动态规划，O(N)

1 int MaxSum(int *arr, int &left, int &right, int n) 2 { 3     if (!arr || n <= 0) { 4         left = -1; 5         right = -1; 6         return IntMin; 7     } 8  9     int nAll = arr[n - 1];10     int nStart = arr[n - 1];11     left = 0;12     right = n - 1;13     for (int i = n - 2; i >= 0; --i) {14         if (nStart < 0) {15             right = i;16             nStart = 0;17         }18         nStart += arr[i];19         if (nStart > nAll) {20             left = i;21             nAll = nStart;22         }23     }24     return nAll;25 }