Maximum Product Subarray
MediumDynamic Programming
You are given an integer array nums. Return the largest product of any non-empty contiguous subarray.
The subarray may be the whole array or a single element. Values can be negative or zero, so multiplying in more numbers can make a product larger or smaller.
Example 1
- Input:
- nums = [-2, 3, -4]
- Output:
- 24
- Explanation
- Multiplying all three gives (-2) * 3 * (-4) = 24, because the two negatives cancel. Any shorter subarray is at most 3.
Example 2
- Input:
- nums = [-3, 0, -2, -4]
- Output:
- 8
- Explanation
- The zero splits the array. On the right, (-2) * (-4) = 8, which beats anything that includes the zero (product 0) or the
-3.
Example 3
- Input:
- nums = [-5]
- Output:
- -5
- Explanation
- The subarray must be non-empty, so the only choice is
-5itself.
Constraints
- 1 ≤
nums.length≤ 2 * 104 - -10 ≤
nums[i]≤ 10 - The product of any prefix or suffix of
numsfits in a signed 32-bit integer