Maximum Product Subarray

link

Key ideas

• We want to have even or 0 negative numbers in the subarray, so that the product will be positive.

• The challenge is we never know if we will eventually get even negative numbers, so we need to maintain 3 variables

  • local_max: the maximum product we can get at nums[i], it's either nums[i] itself, nums[i] * previous_local_max(if nums[i] is positive), or nums[i] * previous_local_min(if nums[i] is negative)
  • local_min: same idea as above
  • global_max: the global max we get so far, which will be the answer at the end.

• The tricky part is if nums[i] is negative, we multiply it by the previous local_min, so it could potentially yield a bigger number. Think of the following examples. In any of the examples, nums[i] * previous_local_min > nums[i] * previous_local_max:

  • nums[i]: -2 / -2 / -2
  • previous_local_max: 2 / -1 / 2
  • previous_local_min: -2 / -2 / 1

def maxProduct(nums) -> int:
    local_max, local_min, global_max = nums[0], nums[0], nums[0]

    for i in range(1, len(nums)):
        previous_max = local_max
        previous_min = local_min
        if nums[i] < 0:
            local_max = max(nums[i], previous_min * nums[i])
            local_min = min(nums[i], previous_max * nums[i])
        else:
            local_max = max(nums[i], previous_max * nums[i])
            local_min = min(nums[i], previous_min * nums[i])
        global_max = max(global_max, local_max)
    return global_max

Note: The key difference between this question and 53. Maximum Subarray is we don't care if we have even negative numbers or not in 53. Maximum Subarray, so we don't need to hold local_max and local_min there.