Maximum Product Subarray — InterviewPrepKit

Solving tips

Unlike Kadane's sum, a product can flip sign, so carry BOTH the max and min product ending at each index.
cur_max = max(x, x*prev_max, x*prev_min); cur_min = min of the same three - a negative x swaps which extreme is best.
Snapshot the old cur_min before overwriting cur_max (or do the negative-swap first), or you corrupt the update.
Seed best = cur_max = cur_min = nums[0], not 0 (fails on [-3]); zeros reset via the standalone x candidate. O(n) time, O(1) space.

Problem

Given an integer array nums, find the contiguous non-empty subarray with the largest product of its elements, and return that product. The array may contain negative numbers and zeros. The answer is guaranteed to fit in a 32-bit integer.

Examples

nums = [2,3,-2,4] → 6 — the subarray [2,3] gives 6; extending past -2 would flip the sign.
nums = [-2,0,-1] → 0 — the best non-empty product is 0 (any window with a negative alone is worse).
nums = [-2,3,-4] → 24 — the whole array: (-2)·3·(-4) = 24; two negatives make a positive.

Constraints

1 <= nums.length <= 2·10⁴
-10 <= nums[i] <= 10
Every prefix/suffix product fits in a 32-bit integer.

Think about it first

Hint 1

For a sum subarray (Kadane), you only track the best running sum. Products are trickier: a large negative running product can become the largest positive the moment you multiply by another negative. So one running value isn't enough.

Hint 2

Track two things ending at each index: the maximum product and the minimum product of a subarray ending there. A new negative number swaps their roles.

Hint 3

cur_max = max(x, x·prev_max, x·prev_min) and cur_min = min(x, x·prev_max, x·prev_min). A zero resets both (starting fresh at x handles that). Track the global best of all cur_max.

TL;DR

Track the running max and min product ending at each index (negatives swap them) — O(n) time, O(1) space.

Approach 1 — Brute force

Compute the product of every contiguous subarray and keep the largest.

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
        best = nums[0]
        for i in range(n):
            prod = 1
            for j in range(i, n):
                prod *= nums[j]
                best = max(best, prod)
        return best

Complexity: O(n²) time, O(1) space. At n = 2·10⁴ that’s ~4·10⁸ multiplications — borderline-to-too-slow, and needless.

Approach 2 — DP with max/min arrays

The insight: unlike sums, a product can flip sign. The largest product ending at i comes from one of three candidates: nums[i] alone, nums[i]·(best positive ending at i-1), or nums[i]·(most negative ending at i-1) — because a negative times a negative is a big positive. So we must carry both extremes forward.

Recurrence: hi[i] = max(nums[i], nums[i]·hi[i-1], nums[i]·lo[i-1]) lo[i] = min(nums[i], nums[i]·hi[i-1], nums[i]·lo[i-1]) Answer = max(hi).

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
        hi = [0] * n
        lo = [0] * n
        hi[0] = lo[0] = nums[0]
        for i in range(1, n):
            x = nums[i]
            a, b, c = x, x * hi[i - 1], x * lo[i - 1]
            hi[i] = max(a, b, c)
            lo[i] = min(a, b, c)
        return max(hi)

Walkthrough (nums = [2,3,-2,4]):

i0: hi=2, lo=2
i1 (3): candidates 3, 6, 6 → hi=6, lo=3
i2 (-2): candidates -2, -12, -6 → hi=-2, lo=-12
i3 (4): candidates 4, -8, -48 → hi=4, lo=-48
max(hi) = max(2,6,-2,4) = 6. ✓

Complexity: O(n) time, O(n) space.

Approach 3 — Space-optimized (two rolling variables)

The insight: each step reads only the previous hi and lo, so keep two scalars. One subtlety: cur_max must be computed from the old cur_min, so snapshot before overwriting.

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        best = cur_max = cur_min = nums[0]
        for x in nums[1:]:
            if x < 0:                       # negative flips the roles
                cur_max, cur_min = cur_min, cur_max
            cur_max = max(x, x * cur_max)
            cur_min = min(x, x * cur_min)
            best = max(best, cur_max)
        return best

Walkthrough (nums = [-2,3,-4]):

start best=cur_max=cur_min=-2
x=3 (≥0): cur_max=max(3,-6)=3, cur_min=min(3,-6)=-6, best=3
x=-4 (<0): swap → cur_max=-6, cur_min=3; then cur_max=max(-4,24)=24, cur_min=min(-4,-12)=-12, best=24. ✓

Complexity: O(n) time, O(1) space.

Common pitfalls

Adapting Kadane’s max-sum idea with a single running value — a lone maximum silently drops the “two negatives make a positive” case ([-2,3,-4] → 24).
Overwriting cur_max before using the old value to compute cur_min — snapshot both, or do the negative-swap trick first.
Zeros: they force both extremes back to x (i.e. 0) via the max(x, x*prev) form, correctly restarting the subarray after the zero.
Initializing best = 0 — wrong for an all-negative single-element array like [-3]; seed from nums[0].

Pattern takeaway

When a running-optimum DP has an operation that can invert which extreme is best (multiplication by a negative, here), carry both the max and the min forward. This “track both extremes” trick generalizes Kadane’s algorithm to any monoid where the best future value can spring from today’s worst value.