Maximum Product Subarray
The briefingthe full drill, in my own words
The drill: Somewhere in an array of integers, one contiguous run multiplies out to the largest product of any run. Find that maximum product.
A list of integers arrives, and the task is to scan every contiguous stretch of it — never skipping around — and multiply the values inside that stretch together. Somewhere among all those possible stretches sits one whose product beats every other stretch's product.
Negative numbers are the whole trick here: a single negative flips the sign of everything it touches, so a very negative running product can vault to the top the moment one more negative value joins it. Zeros act as hard resets, since a zero anywhere kills the product of a run through it.
A run of exactly one number is a valid stretch on its own, so the answer always exists even when every value is negative or the whole array is one number. The output is just the largest product found, not the stretch itself.
- arrays hold at least one integer, so an answer always exists
- values can be negative, zero, or positive
- a single element counts as its own valid run
- arrays stay small enough that O(n) or O(n²) both finish quickly
The hintstake only what you need
HINT 1 THE NUDGE
A running max that only tracks the biggest product so far breaks the moment a negative number shows up — what can a negative number turn a small product into?
HINT 2 THE STRUCTURE
A negative number flips the sign of whatever it multiplies — so the smallest, most negative running product can become the largest the instant one more negative joins it. Track both extremes.
HINT 3 ONE STEP FROM THE ANSWER
At each element compute the new max and new min as the best and worst of (element alone, max·element, min·element) — a negative element is exactly what swaps their roles.
Coach's boardthe pattern, step by step
Negatives flip signs — a very negative running product can vault to the top when one more negative joins it. Track both max AND min.
The splitstwo paces, two languages
class Solution:
def maxProduct(self, nums: List[int]) -> int:
best = cur_max = cur_min = nums[0]
for x in nums[1:]:
candidates = (x, cur_max * x, cur_min * x)
cur_max, cur_min = max(candidates), min(candidates)
best = max(best, cur_max)
return bestclass Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
best = nums[0]
for i in range(n):
product = 1
for j in range(i, n): # extend the run one element at a time
product *= nums[j]
best = max(best, product)
return bestclass Solution {
public int maxProduct(int[] nums) {
int best = nums[0], curMax = nums[0], curMin = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
int a = curMax * x, b = curMin * x;
curMax = Math.max(x, Math.max(a, b));
curMin = Math.min(x, Math.min(a, b));
best = Math.max(best, curMax);
}
return best;
}
}class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int best = nums[0];
for (int i = 0; i < n; i++) {
long product = 1;
for (int j = i; j < n; j++) {
product *= nums[j];
best = (int) Math.max(best, product);
}
}
return best;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED