53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Problem

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

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.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

Constraints:

• 1 <= nums.length <= 2 * 104

• -231 <= nums[i] <= 231 - 1

Solution

1. DP

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

2. Recursive

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSubArray(nums, 0, nums.size() - 1);
    }
    int maxSubArray(vector<int>& nums, int left, int right) {
        if (left > right) return INT_MIN;
        int mid = left + (right - left) / 2;
        int max_sub_left = 0;
        int max_sub_right = 0;
        int sum = 0;
        for (int i = mid + 1; i <= right; ++i) {
            sum += nums[i];
            if (sum > max_sub_right) max_sub_right = sum;
        }
        sum = 0;
        for (int i = mid - 1; i >= left; --i) {
            sum += nums[i];
            if (sum > max_sub_left) max_sub_left = sum;
        }
        return max(
            max(maxSubArray(nums, left, mid - 1), maxSubArray(nums, mid + 1, right)),
            nums[mid] + max_sub_left + max_sub_right
        );
    }
};

• #recursion

• #dp

• #math

• #important