Largest Product Subarray
You get an integer array nums. A subarray is a group of one or more elements that sit next to each other in the array.
Return the largest product of any subarray. The product is all its values multiplied together.
Note
The subarray must have at least one element. The array can contain zeros and negative numbers.
Hint
A negative value turns a very small (very negative) product into a very large one. So for each position keep two values: the largest and the smallest product of a subarray that ends there. When the current value is negative, these two swap roles. A zero resets both. This takes O(n) time.
Examples
Example 1
- Input:
- [2,-5,-2,0,3]
- Output:
- 20
The subarray [2, -5, -2] gives 2 * -5 * -2 = 20. The two negatives cancel each other.
Example 2
- Input:
- [-3,0,-4]
- Output:
- 0
Each single value is -3, 0 or -4. Every longer subarray includes the 0. So the best product is 0.
Example 3
- Input:
- [4,-1,3,-2,-6]
- Output:
- 36
The subarray [3, -2, -6] gives 36. Taking all five values gives 4 * -1 * 3 * -2 * -6 = -144, which is negative because there are three negatives.
Constraints
1 <= nums.length <= 16-9 <= nums[i] <= 9- With these limits every product fits in a normal integer (its size is at most
9^16).
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.