53. Maximum Subarray.md

53. Maximum Subarray

描述：在一个数组中，找到最大的连续子序列和。

1. Divide and Conquer in O(NlogN) time。分治法，子问题划分到最小的时候，return的要么是单个元素，要么是跨中点的子列和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return cal_maxSubArray(nums, 0, nums.size()-1);
    }
private:
    int cal_maxSubArray(vector<int>& nums, int l, int r)
    {
        int i, mid, maxSubArray_L, maxSubArray_R, maxSubArray_M;
        if(l==r) //子问题划分到最小，单个的元素值就是最大子列和。
            return nums[l];
        
        mid = (l+r)/2;
        maxSubArray_L = cal_maxSubArray(nums, l, mid);//左边-最大子列和
        maxSubArray_R = cal_maxSubArray(nums, mid+1, r);//右边-最大子列和
        maxSubArray_M = max_crossing_SubArray(nums, l, r); //跨中点-最大子列和
        
        return max(max(maxSubArray_L, maxSubArray_R), maxSubArray_M);//取三者中的最大值
    }
    
    int max_crossing_SubArray(vector<int>& nums, int l, int r)
    {
        int i, m = (l+r)/2;
        int sum, sum_L=INT_MIN, sum_R=INT_MIN;
        sum = 0; //计算跨中点左半边最大和
        for(i=m; i>=l; i--)
        {
            sum += nums[i];
            sum_L = max(sum_L, sum);
        }
        sum = 0; //计算跨中点右半边最大和
        for(i=m+1; i<=r; i++)
        {
            sum += nums[i];
            sum_R = max(sum_R, sum);
        }
        return sum_L+sum_R; //两者相加
    }
};

2. 在线处理 O(N) time

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(empty(nums))
            return 0;
        
        int sum=0, max_sum=nums[0], i;
        for(i=0; i<nums.size(); i++)
        {
            sum += nums[i];
            max_sum = max(max_sum, sum);
            if(sum<0)
                sum = 0;
        }
        return max_sum;
    }
};

3. 动态规划，Kadane's algorithm

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(empty(nums))
            return 0;
        int res = nums[0];
        int sum = 0;
        int i;
        
        for(i=0; i<nums.size(); i++)     
        {
            //sum = max(sum, sum + nums[i]); //这种写法错误：sum中的元素可能是不连续相邻元素组成的。
            
            sum = max(nums[i], sum + nums[i]); //sum：到元素nums[i]为止的连续元素的最大子列和。
            res = max(res, sum); //一共可算得nums.size()个sum。取最大的sum，保存为res。
        }
        
        return res;
    }
};

References

• 参考1
• 参考2

相关问题：152.Maximum Product Subarray