Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
思路一：动态规划的思想。时间复杂度O(n),空间复杂度O(1)。给出《剑指offer》面试题31的代码，它不仅时空复杂度较好，而且还较好的处理了无效输入的情况。
如果参数为空指针、数组长度小于0的情况。此时返回0。为了区分子数组的最大值是0和无效输入这两种不同的请款。设置一个全局变量来标记是否输入无效。
1 bool g_InvalidInput = false; 2 3 int FindGreatestSumOfSubArray(int *pData, int nLength) { 4 if ((pData == NULL) || (nLength <= 0)) 5 { 6 g_InvalidInput = true; 7 return 0; 8 } 9 10 g_InvalidInput = false; 11 12 int nCurSum = 0; 13 int nGreatestSum = 0x80000000; 14 for (int i = 0; i < nLength; ++i) 15 { 16 if (nCurSum <= 0) 17 nCurSum = pData[i]; 18 else 19 nCurSum += pData[i]; 20 21 if (nCurSum > nGreatestSum) 22 nGreatestSum = nCurSum; 23 } 24 25 return nGreatestSum; 26 }
思路二：分治策略。时间复杂度O(nlgN),空间复杂度O(1)。
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 return maxSubArray(A, 0, n - 1); 5 } 6 7 int maxSubArray(int A[], int low, int high) { 8 if (low == high) return A[low]; 9 10 int mid = (low + high) /2; 11 int max_left_sum = maxSubArray(A, low, mid); 12 int max_right_sum = maxSubArray(A, mid + 1, high); 13 14 int max_cross_leftsum = INT_MIN, cross_leftsum = 0; 15 for (int i = mid; i >= low; --i) { 16 cross_leftsum += A[i]; 17 if (cross_leftsum > max_cross_leftsum) 18 max_cross_leftsum = cross_leftsum; 19 } 20 21 int max_cross_rightsum = INT_MIN, cross_rightsum = 0; 22 for (int i = mid + 1; i <= high; ++i) { 23 cross_rightsum += A[i]; 24 if (cross_rightsum > max_cross_rightsum) 25 max_cross_rightsum = cross_rightsum; 26 } 27 28 int max_cross_sum = max_cross_leftsum + max_cross_rightsum; 29 30 if (max_left_sum >= max_cross_sum && max_left_sum >= max_right_sum) { 31 return max_left_sum; 32 } else if (max_right_sum >= max_cross_sum && max_right_sum >= max_left_sum) { 33 return max_right_sum; 34 } else { 35 return max_cross_sum; 36 } 37 } 38 };
原文：http://www.cnblogs.com/vincently/p/4135517.html