Maximum Product Subarray

Problem Statement

Given an integer array nums, find the subarray that has the largest product and return that product.

Example 1 Input: nums = [2, 3, -2, 4]
Output: 6 → subarray [2, 3]

Example 2 Input: nums = [-2, 3, -4]
Output: 24 → subarray [-2, 3, -4]

nums =

Array

State

maxProd —

minProd —

result —

Candidates at current index

Enter an array and press Run.

0 / 0

speed

Key Insight

Unlike maximum sum subarray, a negative × negative pair can flip the running product back to a large positive. So we can't just track maxProd — we must also track minProd (the most-negative running product).

At each index, the new maxProd is the best of three candidates: nums[i] alone, prevMax × nums[i], or prevMin × nums[i]. The same three choices determine minProd. Both are needed simultaneously before updating either.

def maxProduct(nums):
    maxP, minP, res = nums[0], nums[0], nums[0]

    for n in nums[1:]:
        # freeze prevMax before overwriting
        candidates = (n, maxP * n, minP * n)
        maxP = max(candidates)
        minP = min(candidates)
        res  = max(res, maxP)

    return res
    # Time O(n) · Space O(1)