152. Maximum Product Subarray
You are given an integer array nums. Among all contiguous, non-empty subarrays, find the one whose elements multiply together to the largest value, and return that product (a single integer — not the subarray itself).
Negatives make this trickier than the max-sum version: a deeply negative running product flips into a large positive one the instant another negative arrives, and any zero wipes the running product out entirely.
The test data guarantees that the product of every contiguous subarray fits in a signed 32-bit integer.
Example 1:
Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] multiplies to 6. Including the -2 would flip the sign, and [-2, 4] only reaches -8.
Example 2:
Input: nums = [-2, 0, -1]
Output: 0
Explanation: No subarray beats 0 here: [-2] and [-1] are negative, and any window crossing the middle contains the 0.
Constraints:
- 1 ≤ nums.length ≤ 2 * 10⁴
- -10 ≤ nums[i] ≤ 10
- The product of any contiguous subarray of nums fits in a 32-bit signed integer.
Hints:
Kadane's max-sum recipe does not transfer as-is: the best product ending at index i might be built from the *smallest* (most negative) product ending at i - 1, waiting for one more negative to flip it.
Carry two running values per position — the largest and the smallest product of a subarray ending there. Each new element either starts a fresh subarray or extends one of those two.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 3, -2, 4]
Expected output: 6