Maximum Product Subarray
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
Find the contiguous subarray with the largest product and return that product.
The array is non-empty and every product fits in a 32-bit integer.
Examples
Input: nums = [2,3,-2,4] Output: 6
The subarray [2,3] has product 6.
Input: nums = [-2,0,-1] Output: 0
The best available product is 0.
Constraints
- 1 <= len(nums) <= 2 * 10^4
- -10 <= nums[i] <= 10
Approaches
- Sweep forwards and backwards — time O(n), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
