Problem overview
Given an IntArray named nums, maxProduct returns the largest product of a subarray: a run of one or more elements that stand next to each other. The product is all of the run's elements multiplied together. The constraints say each element is between -10 and 10 and every subarray's product fits in a 32-bit Int.
For [2, 3, -2, 4] the answer is 6, from [2, 3]: the only negative number, -2, turns every subarray that includes it negative. For [-2, 0, -1] the answer is 0, not 2: [-2, -1] is not a subarray, because the 0 sits between them. For [-2, 3, -4] the answer is 24, from the whole array, since the two negative numbers cancel out.
Approach
For a sum, the best subarray ending at position i comes from the best one ending at i - 1: extend it, or start over. A product is trickier because of the signs. A big negative product, multiplied by a negative number, becomes a big positive one. So the smallest product ending just before i can become the largest product ending at i.
The fix is to keep two numbers for each position:
maxHere: the largest product of a subarray that ends at the current element;minHere: the smallest product (the most negative) of a subarray that ends at the current element.
At each new element x = nums[i], the best subarray ending here either starts fresh at x or extends an earlier one. If x is positive, extending uses maxHere for a large product and minHere for a small one. If x is negative, the roles swap: the old minHere times x is the largest candidate and the old maxHere times x the smallest. The lesson does the swap first, then uses the same two formulas for every element. Starting fresh is also how a product recovers after a 0, since 0 * anything is 0.
A brute force that multiplies every subarray looks at a quadratic number of subarrays. The single pass below needs only the three variables.
Step by step
- Largest so far for this end:
var maxHere = nums[0]. At the first element, the only subarray ending there is the element itself. - Smallest for this end:
var minHere = nums[0]. - Best answer so far:
var result = nums[0]. The subarray needs at least one element, so the first element alone is a valid start, even if it is negative. - Loop with
iover1 until nums.size. Element 0 is already accounted for. - Swap on a negative. If
nums[i] < 0, exchangemaxHereandminHerethrough a temporaryval temp. After the swap, each variable is the right one to multiply by the negative number. - Update the maximum:
maxHere = maxOf(nums[i], maxHere * nums[i]): start fresh or extend. - Update the minimum:
minHere = minOf(nums[i], minHere * nums[i]). - Update the answer:
result = maxOf(result, maxHere). The best subarray ends at some element, so checking the best one for every element finds it. - After the loop, return
result.
The solution in Kotlin
class Solution {
fun maxProduct(nums: IntArray): Int {
var maxHere = nums[0]
var minHere = nums[0]
var result = nums[0]
for (i in 1 until nums.size) {
if (nums[i] < 0) {
val temp = maxHere
maxHere = minHere
minHere = temp
}
maxHere = maxOf(nums[i], maxHere * nums[i])
minHere = minOf(nums[i], minHere * nums[i])
result = maxOf(result, maxHere)
}
return result
}
}
A trace
For [-2, 3, -4] the variables change like this:
start: maxHere=-2 minHere=-2 result=-2
i=1 nums[i]=3: maxHere=3 minHere=-6 result=3
i=2 nums[i]=-4: maxHere=24 minHere=-12 result=24
At i = 2 the swap runs first: maxHere becomes -6 and minHere becomes 3. Then -6 times -4 gives 24, a new largest product. For [-2, 0, -1] the trace is:
start: maxHere=-2 minHere=-2 result=-2
i=1 nums[i]=0: maxHere=0 minHere=0 result=0
i=2 nums[i]=-1: maxHere=0 minHere=-1 result=0
The 0 sets both variables to 0, whatever came before, and the result stays 0.
Kotlin details worth knowing
varandval. The three running variables change in the loop, so they arevar.tempis set once per swap, so it isval.maxOfandminOf. These standard-library functions pick the larger or smaller of two values, so noifand no import is needed.1 until nums.size.untilexcludes the end, so the loop covers indexes 1 tonums.size - 1. For an array with one element the range is empty and the loop is skipped.- Swapping two variables. Kotlin has no tuple swap like
a, b = b, a. Three assignments throughtempare the usual way. Intoverflow.Intis 32 bits and wraps silently. Here the guarantee that every subarray's product fits keeps all three variables in range, so noLongis needed.
Complexity
- Time: O(n). One pass, with a constant amount of work per element.
- Space: O(1). A fixed number of variables, whatever the length of the array.
Edge cases and common mistakes
- Tracking only the maximum. A version that keeps only
maxHerereturns 3 for[-2, 3, -4]instead of 24: it forgets that-6, a very small product, is exactly what the second negative number needs. - Starting
resultat 0. For[-3]the answer is -3, because the subarray must have at least one element. Starting atnums[0]handles this. - Zeros. A 0 makes every product that includes it 0, so a subarray can't continue past it with its old product. Because each step also considers starting fresh at
nums[i], the totals restart after the 0, and for[0, 2]the answer is 2. - Several negatives. For
[-2, -3, -4]the answer is 12, from[-3, -4], not from the whole array, whose product is -24. The pair of the two negatives is the best choice. - Doing the swap after the updates. The swap has to come before the two
maxOfandminOflines, because they assume each variable is already the right one for the sign ofnums[i]. - One element.
[0]gives 0 and[-3]gives -3: the loop doesn't run, andresultis the element.
Testing
These results come from running the solution above:
nums | Result |
|---|---|
[2, 3, -2, 4] | 6 |
[-2, 0, -1] | 0 |
[-2, 3, -4] | 24 |
[-3] | -3 |
[0] | 0 |
[-2, -3, -4] | 12 |
[0, 2] | 2 |
[-1, -1] | 1 |
