Maximum Product Subarray

+10

Multiply the elements of a subarray of nums together, and return the largest product any subarray can give. A subarray takes consecutive elements without gaps and is never empty, so even an array of negatives has an answer. Zeros and negative values are allowed.

Function

maxProduct(nums: integer-array) → integer

numsinteger-array: the integers to multiply, each between -10 and 10
Returnsinteger: the largest product of a non-empty subarray

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
The product of every subarray fits in a 32-bit signed integer.

Examples

Input: nums = [2, -5, 3, -2, 0, 4]
Output: 60
Explanation: The two negatives cancel: 2 × -5 × 3 × -2 = 60. The 0 cuts the array in two, and the 4 on the other side cannot beat 60.

Input: nums = [-2, 3, -4, -1]
Output: 24
Explanation: The whole array multiplies to -24 because it holds three negatives. Leaving out the last element keeps two of them: -2 × 3 × -4 = 24, which beats the 12 you get by leaving out the first element.

Input: nums = [-6, 0, -7]
Output: 0
Explanation: A subarray that avoids the 0 is a single negative number, and a subarray that contains the 0 multiplies to 0. The best choice is the subarray [0].

Follow-up

How would you also report where the best subarray starts and ends, still in O(n) time and O(1) space?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Multiplying by a negative number reverses the order of products, so the smallest product so far can become the largest one step later, and a zero wipes every product out. Carry two values at each index instead of one, the largest and the smallest product of a subarray that ends there, and one pass is enough.

Multiply every subarray from each start

Correct, but does not finish on the largest tests

Intuition

Fix a start index and move the end to the right, multiplying a running product by each new element. Comparing it with the best after each step covers every subarray once. Start best at nums[0], since the answer can be negative.

There are about n²/2 pairs of start and end, one multiplication each: 2 × 10^8 for 20,000 elements.

Algorithm

Set best to nums[0].
For each start, set product to 1.
Move end from start to the last index and multiply product by nums[end].
If product is larger than best, store it.
Return best.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

Scan from both ends, restarting at zeros

Intuition

Zeros split the array into zero-free runs. Inside a run every value is at least 1 in size, so a longer subarray never has a smaller absolute product; only the sign changes. With an even number of negatives, the whole run is best. With an odd number, one negative must go, and the best cut drops the first negative and everything before it, or the last negative and everything after it. Either way you keep a suffix or a prefix of the run.

A left pass with a running product checks every prefix, resetting to 1 after a 0. A right pass checks every suffix. On [-2, 3, -4, -1] the left pass sees -2, -6, 24 and -24, the right pass -1, 4, 12 and -24, so the answer is 24. The argument needs every nonzero value to be at least 1 in size, which holds for integers.

Algorithm

Set best to nums[0] and product to 1.
Walk from left to right: multiply product by each element and keep the larger of best and product.
Whenever product becomes 0, set it back to 1 so the next run starts fresh.
Set product to 1 again and make the same walk from right to left.
Return best.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

Track the largest and smallest product ending here

Intuition

Every subarray ending at index i is nums[i] alone, or nums[i] times a subarray ending at i-1. When nums[i] is negative, the largest of those products comes from the smallest product ending at i-1. So keep both: high and low, the largest and smallest products of a subarray ending at the current index. The new high is the largest of num, high × num and low × num, and the new low is the smallest. Taking num alone is what restarts the run after a zero.

In the first example low is -30 when the -2 arrives, and -30 × -2 = 60 becomes high, the answer.

Algorithm

Set high, low and best to nums[0].
For each later element num, compute a = high × num and b = low × num.
Set high to the largest and low to the smallest of num, a and b.
Set best to the larger of best and high.
Return best.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

Pitfalls and edge cases

Tracking only the largest product. On the first example that returns 4 instead of 60, because it drops the -30 that the -2 turns into 60.
Computing the new low from the already updated high. Save high × num and low × num before changing either.
Starting best at 0 or 1. [-3] must return -3, because the subarray cannot be empty.
Running only the left pass of the two-pass method. On [-2, 3, 4] it never sees more than -2, but the suffix [3, 4] gives 12.
In JavaScript, TypeScript and Lua, 0 times a negative number is -0, which prints with a minus sign. Add 0 to the result before returning it.

Frequently asked questions3

What is the time complexity of Maximum Product Subarray?

Tracking the largest and smallest product ending at each index takes O(n) time and O(1) space. The two-pass prefix and suffix method costs the same. Multiplying every subarray from each start takes O(n²) time.

Why do you need the minimum product in Maximum Product Subarray?

A negative number turns the most negative product ending at the previous index into the largest one. Keep only the largest product and that candidate is gone when you need it. In [3, -2, -4], the smallest product before the -4 is -6, and -6 × -4 = 24 is the answer.

How is Maximum Product Subarray different from Maximum Subarray?

For sums, a negative running total only ever hurts, so one value per index is enough. For products, a negative running value can become the best after another negative number, and a zero resets everything. So the product version carries the largest and the smallest product at each index.

def maxProduct(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [2, -5, 3, -2, 0, 4]

Expected Output

Maximum Product Subarray

Function

Constraints

Examples

Hints

Solution

Multiply every subarray from each start

Scan from both ends, restarting at zeros

Track the largest and smallest product ending here

Pitfalls and edge cases

Frequently asked questions3

Similar problems