53. Maximum Subarray

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.

Follow up:

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

// Dynamic Programming
int maxSubArray(vector<int>& nums) { // time: O(n); space: O(n)
    int n = nums.size();
    vector<int> dp(n, 0); // dp[i]: max sum of subarray ending with nums[i]
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = (dp[i - 1] > 0 ? dp[i - 1] : 0) + nums[i];
        res = max(res, dp[i]);
    }
    return res;
}

// Space Optimized Dynamic Programming
int maxSubArray(vector<int>& nums) { // time: O(n); space: O(1)
    int sum = 0, res = nums[0];
    for (int num : nums) {
        sum += num;
        res = max(res, sum);
        if (sum < 0) sum = 0;
    }
    return res;
}

// Divide and Conquer
int maxSubArray(vector<int>& nums) { // time: O(nlogn); space: O(logn)
    if (nums.empty()) return 0;
    return helper(nums, 0, (int)nums.size() - 1);
}
int helper(vector<int>& nums, int l, int r) {
    if (l >= r) return nums[l];
    int mid = l + (r - l) / 2;
    int lmax = helper(nums, l, mid - 1);
    int rmax = helper(nums, mid + 1, r);
    int mx = nums[mid], sum = nums[mid];
    for (int i = mid - 1; i >= l; --i) {
        sum += nums[i];
        mx = max(mx, sum);
    }
    sum = mx;
    for (int i = mid + 1; i <= r; ++i) {
        sum += nums[i];
        mx = max(mx, sum);
    }
    return max({mx, lmax, rmax});
}