53. Maximum Subarray

53. Maximum Subarray

Kadane算法

Whenever you see a question that asks for the maximum or minimum of something, consider Dynamic Programming as a possibility

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSofar = nums[0];
        int maxCur = 0;
        for(auto num : nums)
        {
            maxCur = max(num, num + maxCur);
            maxSofar = max(maxCur, maxSofar);
        }
        return maxSofar;
    }
};

分而知之D&Q

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return find(0, nums.size() - 1, nums);
    }
private:
    int find(int left, int right, vector<int>& nums)
    {
        if(left > right) return INT_MIN;
        
        int mid = (left + right) / 2;
        int cur = 0;
        int maxLeft = 0; // 如果都小于0，那就不采用那边，那么那边的和就是0
        int maxRight = 0;
        
        for(int i = mid - 1; i >= left ; --i)
        {
            cur += nums[i];
            maxLeft = max(maxLeft, cur);
        }
        
        cur = 0;
        
        for(int i = mid + 1; i <= right; ++i)
        {
            cur += nums[i];
            maxRight = max(maxRight, cur);
        }
        
        int bestCombined = nums[mid] + maxLeft + maxRight;
        int leftHalf = find(left, mid - 1, nums); // 这里不用考虑为什么不把mid包含进来，因为如果包含的mid是属于最大的子序列，且只有单边，那么maxRight = 0的情况就已经将其包括了
        int rightHalf = find(mid + 1, right, nums);
        
        return max(bestCombined, max(leftHalf, rightHalf));
    }
};

取中点，往左计算和，往右计算和，这时候有三种情况，中点是最长子串之中的元素，最长子串在中点右边，最长子串在中点左边。对于第一种情况，那就是左+右+中，对于后两种，那么再对左右子串进行同样的查找(DQ)