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.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
方法一：直接暴力破解，时间复杂度可以优化到O(n2)
方法二：使用分治法，假设数组为a[0],a[1],a[2]...a[n-1]，将其分成两部分，一部分为a[0],a[1]...a[n/2-1]和a[n/2],a[n/2+1]...a[n-1]，则原数组的最大字段和为以下三种情况：
1. 原数组的最大字段和与(a[0],a[1]...a[n/2-1])的相同
2. 原数组的最大字段和与(a[n/2],a[n/2+1]...a[n-1])的相同
3. 原数组的最大字段和跨过其中两个元素a[n/2-1]和a[n/2]
此时总的时间复杂度为O(nlogn)，空间复杂度为O(logn)代码如下：
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 return maxSub(A, 0, n-1); 5 } 6 7 int maxSub(int A[], int ibegin, int iend) { 8 if( ibegin > iend ) return 0; 9 if( ibegin == iend ) return A[ibegin]; //如果只有一个元素，则直接返回 10 int mid = ibegin + (iend - ibegin) / 2; //取中，防止溢出 11 int il = maxSub(A, ibegin, mid); //左边部分寻找 12 int ir = maxSub(A, mid+1, iend); //右边部分寻找 13 int sum = A[mid] + A[mid+1]; //开始寻找跨过a[n/2-1]和a[n/2]的最大值 14 int maxsum = sum; 15 for(int i=mid-1; i>=ibegin; --i) { 16 sum += A[i]; 17 maxsum = max(maxsum, sum); 18 } 19 sum = maxsum; 20 for(int i=mid+2; i<=iend; ++i) { 21 sum += A[i]; 22 maxsum = max(maxsum, sum); 23 } 24 return max(maxsum, max(il, ir)); //最后输出3者之中的最大值 25 } 26 };
方法三：动态规划，假设start[i]为a[i],a[i+1]...a[n-1]数组中以a[i]开头的最大字段和，all[i]为a[i],a[i+1]...a[n-1]数组的最大字段和，则有
start[i] = max{a[i], start[i+1]+a[i]}
all[i] = max{start[i], all[i+1]}
此时时间复杂度为O(n)，空间复杂度也为O(n)，不过空间可以优化为O(1)，为便于理解，不作优化处理了，代码如下：
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 int start[n]; //start[i]为a[i],a[i+1]...a[n-1]数组中以a[i]开头的最大字段和 5 int all[n]; //all[i]为a[i],a[i+1]...a[n-1]数组的最大字段和 6 memset(start, 0, sizeof(start)); 7 memset(all, 0, sizeof(all)); 8 start[n-1] = all[n-1] = A[n-1]; //初始化 9 for(int i=n-2; i>=0; --i) { 10 start[i] = max(A[i], start[i+1]+A[i]); 11 all[i] = max(start[i], all[i+1]); 12 } 13 return all[0]; 14 } 15 };
还有一种Kadane算法，相当巧妙，时间复杂度亦为O(n)，空间复杂度为O(1)，具体请问度娘，代码如下：
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 int ans = -0x3fffffff; //预处理最小值 5 int sum = 0; 6 for(int i=0; i<n; ++i) { 7 sum += A[i]; //每次计算连续元素 8 ans = max(ans, sum); //判断ans是否又变大了 9 if( sum < 0 ) sum = 0; //如果sum第一次小于0，立即更新，子数组重新开始 10 } 11 return ans; 12 } 13 };
Maximum Subarray,布布扣,bubuko.com
原文：http://www.cnblogs.com/bugfly/p/3922390.html