152. Maximum Product Subarray
mediumFind the contiguous subarray with the largest product. Trickier than Maximum Subarray — negatives flip signs, so you have to track both the running max AND the running min.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.
Constraints
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Examples
Example 1
nums = [2,3,-2,4]6Explanation: [2,3] has the largest product 6.
Example 2
nums = [-2,0,-1]0Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Sum version (Kadane's) won't work directly because of sign flips.
Hint 2
A negative * negative = positive, so the current minimum can become the new maximum once another negative is multiplied in.
Hint 3
Track BOTH currMax and currMin. At each step the candidates are nums[i] alone, currMax * nums[i], and currMin * nums[i].
Solution approach
Reveal approach
Modified Kadane's tracking max AND min. Initialize currMax = currMin = result = nums[0]. For i = 1..n-1: candidates = [nums[i], currMax * nums[i], currMin * nums[i]]; newMax = max(candidates); newMin = min(candidates); currMax = newMax; currMin = newMin; result = max(result, currMax). The min is tracked because multiplying a large negative min by a future negative can produce the largest positive product. O(n) time, O(1) extra space.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- dynamic-programming
- kadane
Related problems
- 53. Maximum Subarray
- 198. House Robber
- 238. Product of Array Except Self
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
More Dynamic Programming practice problems
- 62. Unique Paths
- 70. Climbing Stairs
- 72. Edit Distance
- 91. Decode Ways
- 96. Unique Binary Search Trees
- 118. Pascal's Triangle
- 120. Triangle
- 122. Best Time to Buy and Sell Stock II