Maximum Product Subarray

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• You have two gotchas for this question:
  • Negative numbers flipping the sign
  • Zero
• First think of what you would do if these gotchas didn’t exist. Then you would simply follow Maximum Subarray, wherein you followed Kadanes Algorithm to store the local maximum and global maximum on every iteration.
• Now let’s add back in this problem. The only difference for the signs is that you should keep track of both the local maximum and the local minimum. This will allow you to check, in each iteration, whether:
  • There are an even number of negative signs, in which case the local maximum has a chance of being overrun by the local minimum.
  • There are an odd number of negative signs, or a positive signed local maximum simply is the local maximum.
• The last case is the 0’s. This is implicitly handled by the code, since when you encounter a 0, nums[i] in the next iteration is itself greater than 0 (since we are doing max(nums[i] * tmp, nums[i] * localMinimum, nums[i]))
• One other case is that the maximum’s encountered so far or the minimum’s encountered so far can be overruled by the element itself. For example:
  • [-1, 8] and just [8] makes 8 the local maximum, and not -8.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        localMinimum, localMaximum = 1, 1
        globalMaximum = nums[0]
        for i in range(len(nums)):
            tmp = localMaximum
            localMaximum = max(nums[i] * tmp, nums[i] * localMinimum, nums[i])
            localMinimum = min(nums[i] * tmp, nums[i] * localMinimum, nums[i])
            globalMaximum = max(globalMaximum, localMaximum)
        return globalMaximum

Cards

START Basic Front: Maximum Product Subarray Back: Keep track of both the local maximum and local minimum in a matter similar to Maximum Subarray.

END

---

References

• Maximum Product Subarray