Dynamic Programming · 079Medium
Maximum Product Subarray
Given an integer array nums, find the contiguous subarray with the largest product and return that product.
Constraints
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- Every prefix or suffix product fits in a 32-bit integer.
Examples
maxProduct([2, 3, -2, 4]) -> 6 // [2,3] maxProduct([-2, 0, -1]) -> 0 maxProduct([-2, 3, -4]) -> 24 // two negatives make a positive maxProduct([-3]) -> -3 // single negative element maxProduct([-1, -2, -9, -6]) -> 108 // all four multiplied maxProduct([0, -3, 0, 2, 2]) -> 4 // [2,2]; zeros reset the run
Edge cases
- Zeros reset the running product.
- A single negative element is its own answer.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — multiply out every subarray.
- Target
- O(n) time, O(1) space — Kadane's variant carrying both the running max and min, swapping them on a negative value.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/079-maximum-product-subarray.js ./practice c 079