Maximum Product Subarray
medium1-D Dynamic Programmingtrack running max and min products (sign flips)B75Solve on LeetCode#152
Given an integer array nums that may contain negatives and zeros, find the contiguous subarray (at least one element) whose elements multiply to the largest product, and return that product.
Constraints: 1 <= nums.length <= 2 * 10^4, -10 <= nums[i] <= 10, and the answer is guaranteed to fit in a 32-bit integer.
Examples
- Input:
- nums = [2, 3, -2, 4]
- Output:
- 6
The subarray [2, 3] gives 6. Extending past the -2 turns the product negative.
- Input:
- nums = [-2, 0, -1]
- Output:
- 0
No subarray avoids ending up at 0 or below: [-2] is -2, [-1] is -1, and anything crossing 0 is 0.
- Input:
- nums = [-2, 3, -4]
- Output:
- 24
The whole array: the two negatives cancel, (-2) × 3 × (-4) = 24.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.