#152 Maximum Product Subarray
the problem
In plain words
Find the contiguous non-empty subarray with the largest product and return that product.
in nums = [2,3,-2,4]
out 6
[2,3].
in nums = [-2,0,-1]
out 0
- 1 ≤ nums.length ≤ 2·10⁴
- −10 ≤ nums[i] ≤ 10
- The product of any subarray fits in a 32-bit int
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternKadane / running best
A negative number turns the smallest product into the largest. So for each position keep both the max and the min product of a subarray ending there.
solutions
From brute force to optimal
Fix a start, extend the end, keep a running product.
- Two loops; update the best after each multiplication.
n(n+1)/2 subarrays, O(1) each thanks to the running product.
A few ints.
class Solution { public int maxProduct(int[] nums) { int best = nums[0]; for (int i = 0; i < nums.length; i++) { int product = 1; for (int j = i; j < nums.length; j++) { product *= nums[j]; // product of nums[i..j] best = Math.max(best, product); } } return best; }}New max = max(x, maxHere·x, minHere·x); new min likewise with min.
- Start all three at nums[0].
- Compute both candidates before overwriting.
- best = max(best, maxHere).
One pass, O(1) per element.
Three ints.
class Solution { public int maxProduct(int[] nums) { // best and worst product of a subarray ENDING here: a negative number swaps their roles int maxHere = nums[0], minHere = nums[0], best = nums[0]; for (int i = 1; i < nums.length; i++) { int x = nums[i]; int a = maxHere * x, b = minHere * x; // both products BEFORE overwriting maxHere = Math.max(x, Math.max(a, b)); // start fresh at x, or extend minHere = Math.min(x, Math.min(a, b)); best = Math.max(best, maxHere); } return best; }}Track the max and the min
in the room
How to say it in the interview
talk track
- Contrast with Kadane for max sum: there one running value is enough; here signs flip, so you need two.
traps
- Updating maxHere before computing minHere with the old maxHere — save both products first.
- A zero resets everything; the
max(x, …)term handles restarting at x.
what they ask next
Follow-ups
Maximum Subarray (LC 53)?
Kadane: cur = max(x, cur + x), best = max(best, cur). One variable.
before you submit
Edge cases to test
- One negative number → that number (the subarray can't be empty).
- Zeros split the array: [-2,0,-1] → 0.
- Two negatives multiply into the best: [-2,3,-4] → 24.
practise next
Similar problems
- #53Maximum SubarrayMediumin Arrays & Strings
- #198House RobberMediumin Dynamic Programming