MediumBlind75ArrayDP
Maximum Product Subarray
Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product.
Examples
Input
nums = [2,3,-2,4]
Output
6
[2,3] has the largest product 6.
Input
nums = [-2,0,-1]
Output
0
The result cannot be subarray of length 1 since [-2,-1] product is 2, but [-2] is -2 and [0] is 0, [-1] is -1. The maximum is 0.
Constraints
- •
1 <= nums.length <= 2 * 10^4 - •
-10 <= nums[i] <= 10 - •
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Approaches
Check all possible subarrays.
CodeT: O(n^2) | S: O(1)
def max_product(nums):
max_prod = float('-inf')
for i in range(len(nums)):
prod = 1
for j in range(i, len(nums)):
prod *= nums[j]
max_prod = max(max_prod, prod)
return max_prodTrack both max and min products (negative * negative = positive).
CodeT: O(n) | S: O(1)
def max_product(nums):
result = max(nums)
cur_min, cur_max = 1, 1
for num in nums:
temp = cur_max
cur_max = max(num, cur_max * num, cur_min * num)
cur_min = min(num, cur_min * num, temp * num)
result = max(result, cur_max)
return resultSame approach with cleaner implementation.
Diagram
nums = [2,3,-2,4]
i=0: max_prod=2, min_prod=2, result=2
i=1: max_prod=6, min_prod=2, result=6
i=2: max_prod=-2, min_prod=-12, result=6
i=3: max_prod=4, min_prod=-48, result=6
CodeT: O(n) | S: O(1)
def max_product(nums):
if len(nums) == 1:
return nums[0]
max_prod = nums[0]
min_prod = nums[0]
result = nums[0]
for i in range(1, len(nums)):
if nums[i] < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(nums[i], max_prod * nums[i])
min_prod = min(nums[i], min_prod * nums[i])
result = max(result, max_prod)
return resultComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check all possible subarrays. |
| DP - Track Min and Max | O(n) | O(1) | Track both max and min products (negative * negative = positive). |
| Optimized DP | O(n) | O(1) | Same approach with cleaner implementation. |
Brute Force
T: O(n^2)S: O(1)
Check all possible subarrays.
DP - Track Min and Max
T: O(n)S: O(1)
Track both max and min products (negative * negative = positive).
Optimized DP
T: O(n)S: O(1)
Same approach with cleaner implementation.
Common Mistakes
Only tracking max product (missing negative*negative case)
Not handling arrays with a single element
Forgetting that the subarray must be contiguous