Maximum Product Subarray

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
1D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Because multiplying by a negative swaps maximum and minimum signs (and multiplying by `0` resets products), track **both** `(curMax, curMin)` ending at `i`: update simultaneously against `x`, `curMax * x`, and `curMin * x`.

2. Complexity Bounds & Proof

Constant state `(curMax, curMin)` per step visits each number once.

3. Minimal Idiomatic Code

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

4. Failure Modes & Interview Follow-ups

Pitfalls:- Clobbering `curMax` before computing `curMin` corrupts the negative-flip product (`save prevMax = curMax` or unpack tuple). - Single-element negative array `[-3]` returns `-3`.
Follow-ups:- Prefix-and-suffix pass computes products forward and backward resetting on `0`; the answer lies in one pass when negative count is even/odd.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Maximum Subarray (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.