[C++]LeetCode: 58 Maximum Subarray

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Anwser 1: Kadane算法

思路：把数组里元素不断往结果里添加，直到sum的值小于0，这时将sum重置为0，同时始终维护一个ans变量，表示子串的和最大值（会获得添加过程中的最大值）。

Attention:

1.sum添加必须从A[0]开始，如果A[0]是负值，则舍弃。

2.判断sum 低于0，则重置0

sum = max(sum, 0);

3.顺序很重要，先比较得到一个较大值，再看是否需重置sum. 维护ans是数组内最大和。

ret = max(ret, sum);
//只把大于0的添加进子序列。
sum = max(sum, 0);

复杂度：O(N)

AC Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        //Idea is very simple. Basically, keep adding each integer to the sequence until the sum drops below 0. If sum is negative, then should reset the sequence.
        int ret = A[0];
        int sum = 0;
        
        for(int i = 0; i < n; i++)
        {
            //必须从A[0]开始加，如果A[0]小于0，则后面判断时舍去A[0]
            sum += A[i];
            ret = max(ret, sum);
            //只把大于0的添加进子序列。
            sum = max(sum, 0);
        }
        return ret;
        
    }
};

分治法：最大子串和的区间有以下三种情况（low，high分别为左右边界，mid为(low+high)/2）：

(1) 区间完全在 A[low,mid-1]
(2) 区间完全在 A[mid+1,high]
(3) 区间包含有 A[mid]

按照这三种情况一直递归下去即可。

Step:

1.  找到数组中间元素，最大子串可能包含或者不包含中间元素。

2.  分开计算

     2.1 如果不包含中间元素，继续在A[low,mid-1] 和 A[mid+1,high]用相同算法查找最大和子串。

     2.2 如果包含，则最大子串，将包含左串的最大后缀和右串的最大前缀

3.  返回三个结果的最大值。

Attention:

1. 注意如何计算最大左后缀和最大右前缀。

2. 注意递归求解左区间和右区间时的范围。

//计算左区间和右区间
        int leftans = maxSubArray_helper(A, left, middle);
        int rightans = maxSubArray_helper(A, middle+1, right);

if(left == right) return A[left];

4. 包含全部元素比较好考虑，不会落下一些值。把middle加入左区间中。

复杂度：O(Nlog(n))

AC Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if(n == 0) return 0;
        maxSubArray_helper(A, 0, n-1);
    }
    
    int maxSubArray_helper(int A[], int left, int right)
    {
        if(left == right) return A[left];
        int middle = left + (right - left)/2;
        
        //计算左区间和右区间
        int leftans = maxSubArray_helper(A, left, middle);
        int rightans = maxSubArray_helper(A, middle+1, right);
        
        //计算含中间元素的区间
        int leftmax = A[middle];
        int rightmax = A[middle+1];
        
        int tmp = 0;
        for(int i = middle; i >= left; i--)
        {
            tmp += A[i];
            leftmax = max(leftmax, tmp);
        }
        
        tmp = 0;
        for(int i = middle+1; i <= right; i++)
        {
            tmp += A[i];
            rightmax = max(rightmax, tmp);
        }
        
        return max(max(leftans, rightans), leftmax + rightmax);
    }
};