53. Maximum Subarray

link

Key ideas

• We can extend the subarray if the sum is still positive after adding the next number
  • If adding the next number makes the sum negative, it means adding the next number doesn't help us get the maximum, we definitely don't want to have it as part of the subarray
  • It's possible that the next number doesn't make the sum negative, but it's still not helpful, for example [3, -2, 1]. Therefore, we want to record the current maximum before the next iteration.

Corner cases

• All the numbers are negative: [-3, -2, -3]
  • we want to compare every single number with the current maximum, so that we can get -2 from the above input.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        i, j = 0, 0
        m = nums[0]
        _m = nums[0] # temporary maximum
        while i < len(nums) and j < len(nums):
            if i == j:
                m = max(nums[i], m)
                _m = nums[i]
            else:
                if _m < 0:
                    i = j 
                    j -= 1
                else:
                    _m += nums[j]
                    # record current maximum before next iteration
                    m = max(_m, m) 
            j += 1
        return m

Runtime: 859 ms, faster than 80.86% of Python3 online submissions for Maximum Subarray.
Memory Usage: 28.6 MB, less than 10.55% of Python3 online submissions for Maximum Subarray.