题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

分析

• 分治法O(NlogN)

首先，我们可以把整个序列平均分成左右两部分，答案则会在以下三种情况中：
1、所求序列完全包含在左半部分的序列中。
2、所求序列完全包含在右半部分的序列中。
3、所求序列刚好横跨分割点，即左右序列各占一部分。
前两种情况和大问题一样，只是规模小了些，答案就是三个结果的最大值。

以分割点为起点向左的最大连续序列和、以分割点为起点向右的最大连续序列和，这两个结果的和就是第三种情况的答案

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return helper(nums,0,nums.size()-1);
    }
    
    int helper(vector<int>& nums, int left, int right){
        if(left>right) return INT32_MIN;
        int mid=(left+right)/2;
        int leftMax=0, rightMax=0;
        int sum=0;
        for(int i=mid-1; i>=left; i--){
            sum+=nums[i];
            leftMax=max(leftMax,sum);
        }
        sum=0;
        for(int i=mid+1; i<=right; i++){
            sum+=nums[i];
            rightMax=max(rightMax,sum);
        }
        
        int midRes = leftMax+rightMax+nums[mid];
        int leftRes = helper(nums,left,mid-1);
        int rightRes = helper(nums,mid+1,right);
        return max(midRes,max(leftRes,rightRes));
    }
};

• 动态规划O(N)

dp[n] = max(0, dp[n-1]) + num[n]

整个问题的答案是max(dp[m])，m∈[1, N]

max可以使用a>b?a:b代替

不要初始化为0，可能全负数

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0) return INT32_MIN;
        int res = nums[0];
        int sum = nums[0];
        if(nums.size() == 1) return res;
        for(int i=1; i<nums.size(); i++){
            sum = max(sum+nums[i],nums[i]);   // sum是以nums[i]结尾的子数组中最大的
            res = max(res,sum);   // res是所有子数组中最大的
        }
        return res;
    }
};