53_MaximumSubarray - a920604a/leetcode GitHub Wiki

class Solution {
public:
    int Divide(vector<int>&nums, int l, int r){
        if(l>=r) return nums[l];
        int mid = l+ (r-l)/2;
        int lmax = Divide(nums, l, mid-1);
        int rmax = Divide(nums, mid+1, r);
        int mmax = nums[mid];
        int temp = nums[mid];
        
        for(int i=mid-1;i>=l;--i){
            temp+=nums[i];
            mmax = max(temp, mmax);
        }
        temp = mmax;
        for(int i=mid+1;i<=r;++i){
            temp+=nums[i];
            mmax = max(temp, mmax);
        }
        return max(max(lmax, rmax), mmax);
    }
    int maxSubArray(vector<int>& nums) {
        return Divide(nums, 0, nums.size()-1);
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //      -1  1   -3  4   -1  2   1   -5  4
        //dp    -1  1   -2  4   3   5   6   1   5
        
        int n = nums.size(), ret = nums[0];
        vector<int>dp(n, INT_MIN);
        dp[0] = nums[0];
        for(int i=1;i<n;++i){
            dp[i] = max(dp[i-1]+ nums[i], nums[i]);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int local = 0, global = INT_MIN;
        for(int n:nums){
            local = max(local+n, n);
            global = max(local, global);
        }
        return global;
        
    }
};