Maximum Product Subarray
Medium
Given an integer array nums, find a contiguous subarray that contains at least one number and has the largest product.
Return the maximum product.
Example 1
Input
nums = [2, 3, -2, 4]
Output
6
Explanation
The subarray [2, 3] has the maximum product:
2 × 3 = 6
Therefore, the answer is 6.
Example 2
Input
nums = [-2, 0, -1]
Output
0
Explanation
The possible products include:
[-2] = -2
[0] = 0
[-1] = -1
[-2, 0] = 0
[0, -1] = 0
Therefore, the maximum product is 0.
Constraints
1 <= n <= 2 * 10^4
-10 <= nums[i] <= 10
The array contains at least one element.
Hints:
Hint 1
For each position, keep track of both:
- Maximum product ending at the current position.
- Minimum product ending at the current position.
Hint 2
A negative number can turn the minimum product into the maximum product.
Auto
Loading editor...
Input
Expected Output