#152

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Product Subarray

Find the subarray with the largest product in an integer array using dynamic programming techniques.

Problem Statement

Given an integer array nums, find the subarray that has the largest product and return that product. The product of any subarray of nums is guaranteed to fit in a 32-bit integer. Consider edge cases such as the presence of negative numbers or zeroes, which might impact the maximum product.

The challenge is to find the optimal way to solve this problem efficiently with a time complexity of O(n), utilizing dynamic programming techniques. By maintaining the maximum and minimum products as you traverse the array, the problem becomes solvable without recalculating the products for each subarray individually.

Examples

Example 1

Input: nums = [2,3,-2,4]

Output: 6

[2,3] has the largest product 6.

Example 2

Input: nums = [-2,0,-1]

Output: 0

The result cannot be 2, because [-2,-1] is not a subarray.

Constraints

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Solution Approach

Dynamic Programming with State Transitions

We maintain two variables, maxProduct and minProduct, to track the maximum and minimum products of subarrays ending at each index. This helps in efficiently computing the largest product by considering the effect of negative numbers. At each step, we update maxProduct and minProduct based on the current number.

Handling Negative Numbers

Negative numbers pose a challenge because multiplying two negative numbers can result in a positive product. Hence, we must consider both the maximum and minimum products up to the current index. The dynamic transition ensures that we choose the correct product based on whether we encounter a negative number.

Space Optimization

Instead of storing the product for all subarrays, we optimize space by only keeping track of the current max and min products. This reduces the space complexity to O(1), while still maintaining the ability to compute the correct maximum product as we iterate through the array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n) because we only need to iterate through the array once. The space complexity is O(1) due to the constant space used to track the maximum and minimum products. This solution is optimal compared to approaches that require storing products of all subarrays, which would result in O(n^2) space complexity.

What Interviewers Usually Probe

Can the candidate explain how negative numbers affect the product and how this is handled in the solution?
Does the candidate demonstrate an understanding of dynamic programming techniques, specifically state transition?
How efficiently can the candidate discuss and apply space optimization in dynamic programming problems?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle negative numbers correctly and assuming that the largest product will always be from the largest values.
Not considering zero as a product, which could reset the subarray product.
Using excessive space by storing all subarray products instead of just tracking the current max and min products.

Follow-up variants

Modify the problem to consider circular subarrays where the subarray can wrap around the array.
Extend the problem to handle larger integer ranges, potentially using BigInteger or similar data types.
Introduce a constraint where the array has multiple zeroes, and check if the algorithm handles this efficiently.

FAQ

What is the key pattern used to solve the Maximum Product Subarray problem?

The problem uses dynamic programming with state transitions, where you maintain both the maximum and minimum products to handle the effect of negative numbers.

How do negative numbers impact the Maximum Product Subarray problem?

Negative numbers flip the product sign. Thus, we track both the maximum and minimum products to ensure we can get the correct result when multiplying two negative numbers.

What is the time complexity of the solution for the Maximum Product Subarray problem?

The time complexity is O(n), as we only need to iterate through the array once, updating the max and min product values at each index.

Can the solution be optimized further?

The space complexity can be optimized to O(1) by only storing the current maximum and minimum products, which reduces unnecessary space usage.

How does the space optimization work in the Maximum Product Subarray solution?

Instead of storing the product for all subarrays, we only keep track of the maximum and minimum product up to each index, which reduces the space complexity to constant space O(1).

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = f = g = nums[0]
        for x in nums[1:]:
            ff, gg = f, g
            f = max(x, ff * x, gg * x)
            g = min(x, ff * x, gg * x)
            ans = max(ans, f)
        return ans

Continue Practicing

#140 word break ii #139 word break #174 dungeon game