53_Maximum Subarray

[Easy][Array, Dynamic Programming]

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.

Solution 1: dynamic programing, bottom-up

Idea:

• If we have the solution for nums[0, n-1], what's the solution when we add one extra integer nums[n-1]? There are two possibilities for the max in nums[0, n]:

  1. nums[n-1] is not included: in this case the max in nums[0, n] equals to the max in nums[0, n-1].

  2. nums[n-1] is included: in this case we need to know the max in nums[0, n-1] that includes nums[n-2], which we call curMaxSum. Then update curMaxSum with the max of two cases: 1) just have nums[n-1] itself; 2) add nums[n-1] to curMaxSum.

• Need to store two values when we iterate over the nums: 1) the max of sum for any subarray; 2) the max of sum for subarray includes the last element.

Time Complexity: $O(n)$

Space Complexity: $O(1)$

def maxSubArray(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    curMaxSum, maxSum = -sys.maxint, -sys.maxint
    for num in nums:
        curMaxSum = max(curMaxSum+num, num)
        maxSum = max(maxSum, curMaxSum)
    return maxSum

Solution 2: Divide and Conquer, Recursive

Idea:

1. divides the array into left and right halves and recursively solves for both of them to get the max sum for each half.

2. For the right half, compute the max sum if the first element is included.

3. For the left half, compute the max sum if the last element is included.

4. Merge: the result for the combination of the 2 sub arrays is the maximum of the following : 1. solution for left sub array, 2. solution for right sub array, 3. max sum in the left subarray with the last element + max sum in the right array with the first element

Time Complexity: $O(n\log{n})$

Space Complexity: $O(1)$

def maxSubArray(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    def helper(left, right):
        if left == right:
            return nums[left]

        # split into two parts
        mid = left + (right - left)//2
        l, r = helper(left, mid), helper(mid + 1, right)

        # max sum if include the first element in the right part
        # linear search
        l1, m1 = nums[mid + 1], nums[mid + 1]
        for i in range(mid + 2, right + 1):
            l1 += nums[i]
            if l1 > m1:
                m1 = l1

        # max sum if include the last element in the left part
        # linear search        
        l2, m2 = nums[mid], nums[mid]
        for i in range(mid - 1, left - 1, -1):
            l2 += nums[i]
            if l2 > m2:
                m2 = l2

        return max(l, r, m1 + m2)

    return helper(0, len(nums) - 1)