You are given an integer array nums. Find the contiguous, non-empty subarray whose elements multiply together to give the largest product, and return that product.
A subarray of a single element counts — its product is simply that element. The tests are constructed so that the answer (and every subarray product along the way) fits in a 32-bit integer.
curMin * x can exceed curMax * x when x < 0. On [-2, 3, -4] the running minimum -6 becomes the winning 24 — tracking only the maximum answers 3.x = 0, max(x, curMax * x) and min(x, curMin * x) both become 0, so the scan restarts after the zero. best already remembered everything before it.nums = [-2] the answer is -2. That is why best is initialized to nums[0], never to 0 or 1.x either extends the previous one or starts fresh at x. The x term is the restart option — dropping it forces every subarray to stretch back to index 0.x, its start becomes the current index; when it extends, the start is inherited (and swapped when the runners swap). Record the (start, end) pair whenever best improves.Input: nums = [2,3,-2,4] Output: 6 The subarray [2,3] has the largest product, 2 × 3 = 6.
Input: nums = [-2,0,-1] Output: 0 The answer cannot be 2 because [-2,-1] is not contiguous. The best we can do is the single element [0].
- 1 <= nums.length <= 2 * 10^4 - -10 <= nums[i] <= 10 - The product of any subarray of nums is guaranteed to fit in a 32-bit integer.
One stray minus sign can turn a fortune into a debt — and a second one can turn it right back. This problem looks like a one-line tweak to maximum subarray sum, but negatives and zeros break the classic running-best trick in a beautiful way. The fix costs exactly one extra variable.
[2,3] is a subarray of [2,3,-2,4], but [3,4] is not.In plain English: slide over every contiguous run of numbers and multiply them; report the biggest product any run achieves. Formally: over all pairs i <= j, maximize nums[i] * nums[i+1] * … * nums[j], and return that maximum (the subarray must contain at least one element).
Worked example 1 — nums = [2, 3, -2, 4]
[2] → 2 [2, 3] → 6 ✓ largest [2, 3,-2] → -12 [-2, 4] → -8 answer: 6
Worked example 2 — nums = [-2, 0, -1]
[-2] → -2 [-2, 0] → 0 [0] → 0 ✓ largest [-2, 0,-1] → 0 answer: 0 (we may NOT skip the 0 to pair -2 with -1)
Asking two or three sharp questions before coding shows an interviewer you think about inputs before algorithms.
“Can the array contain zeros and negative numbers?”
Yes — and they are the whole difficulty. Zeros wipe out any running product; negatives flip its sign.
“Is the subarray required to be non-empty?”
Yes. That means the answer can be negative — for nums = [-2] the answer is -2, so you cannot initialize the best to 0 or 1.
“What if every element is negative?”
With an even count the whole array may win; with an odd count you must drop one end. Try [-2, 3, -4] versus [-2, -3, -4] by hand.
“What should a single-element array return?”
That element itself, even if negative — the product of a one-element subarray is the element.
“How large can the array get?”
Up to 2 * 10^4 elements. The O(n^2) brute force does about 2 * 10^8 multiplications — right at the edge of a time limit — so the interviewer expects the O(n) scan.
“Can intermediate products overflow?”
The tests guarantee every subarray product fits in a 32-bit integer, so plain ints are safe here — but it is a great thing to say out loud.
Before I start, I have a few clarifying questions.
Can the array contain zeros and negatives, and is the subarray required to be non-empty?
I will assume products fit in a 32-bit integer since the constraints guarantee it — otherwise I would flag overflow.
One edge case I want to handle explicitly: a single negative element, where the answer itself is negative.
For sums, the best subarray ending at index i is easy: extend the previous best or restart. For products, a terrible running product can be one multiplication away from being the best one.
nums = [-2, 3, -4] best ending at 3 : 3 (running max) worst ending at 3 : -6 (running min ← looks useless) then x = -4 arrives : -6 × -4 = 24 ← the worst became the best!
At every index keep curMax and curMin, the largest and smallest products of a subarray ending exactly there. Each new element x has only three candidates: x alone (restart), curMax * x, or curMin * x. When x is negative, curMax and curMin simply swap roles.
Any product through a 0 is 0, so at a zero both runners become max(0, …) = 0 and min(0, …) = 0 — the scan effectively restarts after the zero without any special-case code. The answer for a segment is still tracked because best already saw everything before the zero.
| Brute force | Optimal | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(1) |
Both are implemented in full — with a dry run each — in the Approaches selector below.
Key takeaway
Kadane's running-best idea survives the jump from sums to products with one twist: because a negative factor reverses order, you must carry the minimum product ending here alongside the maximum — today's worst is one minus sign away from being tomorrow's best.
best = curMax = curMin = nums[0]
for each x in nums[1:]:
if x < 0: swap(curMax, curMin)
curMax = max(x, curMax * x)
curMin = min(x, curMin * x)
best = max(best, curMax)
return best