Maximum Product Subarray

Problem

https://leetcode.com/problems/maximum-product-subarray/

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

The test cases are generated so that the answer will fit in a 32-bit integer.

Note that the product of an array with a single element is the value of that element.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

• 1 <= nums.length <= 2 * 10:sup:`4`

• -10 <= nums[i] <= 10

• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Pattern

Array, Dynamic Programming

Approaches

Dynamic Programming

Explanation

If we scan left to right, at each index we must decide whether to extend the current subarray or start over. However, because multiplying by a negative number flips the sign, the most negative product ending at the previous index can become the most positive after one multiplication. This means we need to track the maximum and minimum product, because the minimum might produce the next maximum.

At each index i, the candidates for the new maximum product are: 1. nums[i] (start fresh) 2. max_product * nums[i] (extend a positive run) 3. min_product * nums[i] (negative flips to positive)

We also compute the minumum from these 3 candidates. The final answer is the largest max_product seen across all indices.

Code

def maxProduct(nums: list[int]) -> int:
    """Given an integer array ``nums``, return the maximum product of all
    subarrays.
    """
    max_product = nums[0]
    min_product = nums[0]
    result = nums[0]

    for num in nums[1:]:
        candidates = [num, max_product * num, min_product * num]
        max_product = max(candidates)
        min_product = min(candidates)
        result = max(result, max_product)

    return result

Test

>>> from maximum_product_subarray__dynamic_programming import maxProduct
>>> maxProduct([2, 3, -2, 4])
6
>>> maxProduct([-2, 0, -1])
0

Complexity

\(n\) is the number of elements in nums

Measure	Complexity	Notes
Time	\(O(n)\)	one pass through the array
Auxiliary Space	\(O(1)\)	3 variables: max_product, min_product, and result

maximum_product_subarray__dynamic_programming.maxProduct(nums: list[int]) → int

Given an integer array nums, return the maximum product of all subarrays.