Maximum Subarray

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

Read more about this problem on Wikipedia.

# Solution

The brute force solution would:

  • enumerate subarrays in a nested for loop - squared
  • calculate sum - constant
  • update if current subarray has largest sum - constant

So in total it takes squared time.

# Prefix Max

Pick the locally optimal move at each step, and that will lead to the globally optimal solution.

Iterate over the array and update at each step:

  • current element
  • current local maximum sum (at this given point)
  • global maximum sum seen so far

Complexity:

  • time: O(n)O(n)
  • space: O(1)O(1)
def maxSubArray(self, nums: List[int]) -> int:
    n = len(nums)
    curr_sum = max_sum = nums[0]

    for num in nums[1:]:
        curr_sum = max(num, curr_sum+num)
        max_sum = max(curr_sum,max_sum)
    return max_sum

# DP (Kadane's algorithm)

DP logic:

  • if nums[i-1]>0, include i-1th element
  • if nums[i-1]<=0, start a new array from ith element

Modify the array to track the current local max sum, then update the global max sum res.

def maxSubArray(self, nums: List[int]) -> int:
    n = len(nums)
    res = nums[0]

    for i in range(1,n):
        if nums[i-1]>0:
            nums[i] += nums[i-1]
        res = max(res, nums[i])
    return res

# Divide & Conquer (REDO)

Complexity:

  • time: O(nlogn)O(n \log n)
  • space: O(logn)O(\log n)
Last Updated: 7/19/2020, 3:45:14 PM