Find the maximum product subarray in a given array.
Medium
Unlock detailed company stats for this questionUpgrade
Given an integer array nums, find the contiguous subarray with the largest product and return that product. A subarray contains at least one element.
Example 1
Input: nums = [2, 3, -2, 4] Output: 6
The subarray [2, 3] has the largest product.
Example 2
Input: nums = [-2, 0, -1] Output: 0
No subarray has a positive product. The best you can do is 0, from any subarray that includes the 0.
Constraints
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10- The product of any subarray fits in a 32-bit integer.
Approach
Trying every subarray takes O(n²) time. For sums, Kadane's algorithm gets you to O(n) by keeping the best total that ends at each index. Products need one more piece of state: a large negative product becomes the largest positive product the moment you multiply it by another negative number. So carry both the largest and the smallest product that end at the current index.
Steps
- Set
cur_max,cur_minandbesttonums[0]. - For each later value
x, compute three options:x,x * cur_maxandx * cur_min. - Set
cur_maxto the largest option andcur_minto the smallest. - Update
bestwithcur_max. Returnbestafter the loop.
Complexity
- Time:
O(n). You visit each value once. - Space:
O(1). You only store three numbers.
Common mistakes
- Updating
cur_maxfirst and then computingcur_minfrom the new value. Compute both from the previous values. - Treating
0as a special case. Includingxon its own as an option already restarts the product after a zero.
Related questions
Find the maximum subarray productFind the maximum length sub-array with a given sum.Find the maximum subarray sum.Related courses
Course
Course
Course