Maximum Product Subarray — Solution in Python, Java & C++
Maximum Product Subarray solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Product Subarray is a medium coding problem on arrays and dynamic programming, asked in Morgan Stanley interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, find a contiguous non-empty subarray with the largest product and return that product.
Example 1
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product, 6.
Example 2
Input: nums = [-2,0,-1]
Output: 0
Explanation: The answer cannot be 2 because [-2,-1] is not contiguous.
Constraints
1 <= nums.length <= 12-5 <= nums[i] <= 5
Hints for Maximum Product Subarray
Hint 1
A negative number flips the sign — the smallest product so far can become the largest.
Hint 2
Track both the maximum AND minimum product ending at each position.
How to solve Maximum Product Subarray
Kadane's trick does not transfer directly, because multiplying by a negative number turns the smallest running product into the largest. So carry two values at each position — the maximum and the minimum product ending there — and let a negative element swap their roles.
Approach
- Seed both the running maximum and running minimum with the first element, along with the best answer.
- For each later element
x, form three candidates:xalone,x * runningMax, andx * runningMin. - The new running maximum is the largest of the three; the new running minimum is the smallest.
- Compute both from the old values before overwriting either.
- Update the global best with the new running maximum.
Why it works
The largest product ending at a position comes either from starting fresh or from extending the previous subarray — and if x is negative, extending the most negative previous product is what produces the largest new one. Tracking the minimum alongside the maximum is exactly what keeps that possibility available. A zero resets both, which is correct: no subarray spanning it can beat starting over.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Compute the new max and min from the old pair — overwriting the max first and then using it for the min is the classic bug.
- Include
xon its own among the candidates, which is what performs the restart after a zero. - Seed from
nums[0], not1or0; the subarray must be non-empty. - Two negatives multiply to a positive, so a long stretch of negatives can be the answer.
Reference solution
Python
from typing import List
def maxProduct(nums: List[int]) -> int:
best = hi = lo = nums[0]
for x in nums[1:]:
cands = (x, hi * x, lo * x)
hi = max(cands)
lo = min(cands)
best = max(best, hi)
return bestJava
public static int maxProduct(int[] nums) {
int curMax = nums[0], curMin = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
int a = x, b = x * curMax, c = x * curMin;
curMax = Math.max(a, Math.max(b, c));
curMin = Math.min(a, Math.min(b, c));
if (curMax > best) best = curMax;
}
return best;
}C++
int maxProduct(vector<int>& nums) {
int curMax = nums[0], curMin = nums[0], best = nums[0];
for (int i = 1; i < (int) nums.size(); i++) {
int x = nums[i];
int a = x, b = x * curMax, c = x * curMin;
curMax = max(a, max(b, c));
curMin = min(a, min(b, c));
if (curMax > best) best = curMax;
}
return best;
}JavaScript
var maxProduct = function(nums) {
let best = nums[0], hi = nums[0], lo = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
const a = x, b = hi * x, c = lo * x;
hi = Math.max(a, b, c);
lo = Math.min(a, b, c);
best = Math.max(best, hi);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming