Leetcode: 53. Maximum Subarray

• Pattern: Find optimal subarray.
• Pattern: Problem's constraints disallow \(O(n^2)\) solutions.

• Can we formulate the problem as sliding window?
• How can we extend the solution for i to i+1?

Let's start by re-stating the problem in terms of Fix One and Search Other Template. For each \(i\) representing the right-most indexed of the subarray, search the right-most index \(j\) such that \(nums[j] + nums[j+1] + ... + nums[i]\) is maximum. To search in constant time, we have to compute the value of \(j\) knowing something about \(nums[0,1,...,i]\) or have this information already computed as we iterated over each index \(i\). Let's use the second option. As we iterate over indexes \(i\), compute \(cur\) which means the maximum subarray sum ending on \(i\). Let \(prev\) be the maximum subarray sum ending on \(i-1\). We can write \(cur\) in terms of \(prev\) since \(cur = nums[i]\) if \(prev+nums[i]<0\) (starting a new subarray) or \(cur = prev + nums[i]\). After this iteration, \(prev\) becomes \(cur\) and we continue to the next iteration. Time complexity is \(O(n)\) and space is \(O(1)\).

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = cur = nums[0]
        for n in nums[1:]:
            cur = n if cur < 0 else n + cur
            ans = max(ans, cur)
        return ans

• Interview preparation: V
• Leetcode: 152. Maximum Product Subarray