#152
Maximum Product Subarray
Medium Kadane with min & max
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the contiguous subarray with the largest product and return the product.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the contiguous piece with the biggest product.
Why this works: a negative number flips the smallest product into the biggest, so track both the max and the min ending here.
Example: [2, 3, -2, 4]
max/min: 2/2, 6/3, -2/-12, 4/-48best = 6
✦Hints open one at a time
A negative number turns the smallest product into the largest.
Track both the maximum and the minimum product ending at each index.
↗Approach
For each x, the new max is the largest of x, x × oldMax and x × oldMin; the new min is the smallest of the same three. Keep the best max seen.
</>Solution (Java)
class Solution {
public int maxProduct(int[] nums) {
int max = nums[0], min = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
int a = x * max, b = x * min; // use old values
max = Math.max(x, Math.max(a, b));
min = Math.min(x, Math.min(a, b));
best = Math.max(best, max);
}
return best;
}
}!Common mistake
Updating max first and then using the new max to compute min — save the old values first.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Kadane, Dutch Flag & Moore's Voting
🎬 Episodes 11–13: video coming soon