Maximum Product Subarray

How you get there

1. 1A large negative times another negative becomes a large positive, so the minimum matters too.
2. 2Carry both the running max and the running min through each element.
3. 3On a negative element the two swap roles, which is the whole trick.

Solution

def max_product(nums: list[int]) -> int:
    best = cur_max = cur_min = nums[0]
    for x in nums[1:]:
        candidates = (x, cur_max * x, cur_min * x)
        cur_max, cur_min = max(candidates), min(candidates)
        best = max(best, cur_max)
    return best

Time

O(n)

Space

O(1)

What goes wrong

Updating cur_max before cur_min uses the new value in the old one's computation — assign them together.