Maximum Product Subarray

Intuition

A negative number flips the roles of your best and worst running products: the most negative product suddenly becomes the most positive when multiplied by another negative. So at each step you keep two values, the maximum and minimum product ending here, and when the current element is negative you swap them before updating. Each new product is either the element on its own or the element times the previous running extreme, and the overall answer is the best maximum seen anywhere.

Algorithm walkthrough

1. 1Seed the answer, the running maximum, and the running minimum all with the first element.
2. 2For each following element, if it is negative swap the running maximum and minimum first.
3. 3Set the running maximum to the larger of the element alone or the element times the old running maximum.
4. 4Set the running minimum to the smaller of the element alone or the element times the old running minimum.
5. 5Update the answer with the running maximum, and after the loop return that answer.

Implementation

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        best = nums[0]
        cur_max = nums[0]
        cur_min = nums[0]
        for i in range(1, len(nums)):
            x = nums[i]
            if x < 0:
                cur_max, cur_min = cur_min, cur_max
            cur_max = max(x, cur_max * x)
            cur_min = min(x, cur_min * x)
            best = max(best, cur_max)
        return best