DSA problem
Maximum Product Subarray
Given an integer array nums, find a subarray that has the largest product, and return that product.
A subarray is a contiguous non-empty sequence of elements within an array. The test cases are generated so that the answer will fit in a 32-bit integer.
Unlike the sum variant, products are tricky because a negative number flips the sign: multiplying two negatives produces a large positive. The trick is to track both the maximum and minimum product ending at each index, since the current minimum can become the next maximum when multiplied by a negative value.
Examples
Example 1
Input:
nums = [2,3,-2,4]Output:
6Explanation: The subarray [2,3] has the largest product 6.
Example 2
Input:
nums = [-2,0,-1]Output:
0Explanation: The result cannot be 2 because [-2,-1] is not a contiguous subarray; the best contiguous product is 0.
Example 3
Input:
nums = [-2,3,-4]Output:
24Explanation: The whole array [-2,3,-4] has product (-2) * 3 * (-4) = 24, since the two negatives multiply to a positive.
Constraints
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any subarray of nums is guaranteed to fit in a 32-bit integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.