Problem overview
max_product receives a vector nums of integers and returns the largest product of a subarray: a run of one or more neighbouring elements, all multiplied together. For [2, 3, -2, 4] the answer is 6, from [2, 3]; the only negative number, -2, makes every subarray that includes it negative. For [-2, 0, -1] the answer is 0: [-2, -1] isn't a subarray, because the 0 stands between them. For [-2, 3, -4] the answer is 24: the two negatives cancel out over the whole array.
The statement asks for O(n) time and O(1) extra space.
Approach: track the largest and the smallest product ending here
The brute force multiplies every subarray, which is O(n²) pairs of ends for a vector of up to 100,000 elements, too slow. A single pass is possible once you notice that the best subarray must end somewhere, so it is enough to know, for each position, the best product of a subarray ending there.
For a sum, the best subarray ending at element i either starts fresh at i or extends the best one ending at i - 1. A product behaves differently because of signs: a very negative product, multiplied by a negative number, becomes a very positive one.
So the pass keeps two numbers for the subarrays that end at the current element: the largest product, max_here, and the smallest (most negative) one, min_here. A third variable, result, records the largest max_here seen so far.
At each new element x, the candidates for a subarray ending there are x alone, max_here * x and min_here * x. When x is negative, multiplying flips the order: the old smallest product gives the new largest. Swapping max_here and min_here before multiplying takes care of that, so afterwards the larger of "x alone" and "max_here * x" is the new maximum, and the smaller of "x alone" and "min_here * x" is the new minimum. Starting fresh at x is also how a 0 resets the run.
Running it on the examples gives these values at each element:
[2, 3, -2, 4]: start max=2 min=2 res=2 | x=3 max=6 min=3 res=6 | x=-2 max=-2 min=-12 res=6 | x=4 max=4 min=-48 res=6
[-2, 3, -4]: start max=-2 min=-2 res=-2 | x=3 max=3 min=-6 res=3 | x=-4 max=24 min=-12 res=24
[-2, 0, -1]: start max=-2 min=-2 res=-2 | x=0 max=0 min=0 res=0 | x=-1 max=0 min=-1 res=0
Step by step
- Create
max_hereaslet mut, starting atnums[0]. At the first element, the only subarray ending there is the element itself. - Create
min_herethe same way, alsonums[0]. - Create
resultthe same way. A subarray needs at least one element, so the first element alone is a valid start, even when it is negative. - Loop
iover1..nums.len(). Element 0 is already counted. - Swap when
nums[i]is negative, withstd::mem::swap(&mut max_here, &mut min_here). After the swap, each variable is the right one to multiply bynums[i]. - Update
max_heretonums[i].max(max_here * nums[i]): start fresh atior extend. - Update
min_heretonums[i].min(min_here * nums[i]), the same two choices, keeping the smaller product. - Update
resulttoresult.max(max_here). The best subarray ends at some element, so the maximum over everymax_hereis the answer. - Return
resultwith no semicolon.
The solution in Rust
impl Solution {
fn max_product(nums: Vec<i32>) -> i32 {
let mut max_here = nums[0];
let mut min_here = nums[0];
let mut result = nums[0];
for i in 1..nums.len() {
if nums[i] < 0 {
std::mem::swap(&mut max_here, &mut min_here);
}
max_here = nums[i].max(max_here * nums[i]);
min_here = nums[i].min(min_here * nums[i]);
result = result.max(max_here);
}
result
}
}
Rust details worth a closer look:
mut. All three variables change inside the loop, so they are declared withlet mut. Rust infersi32fromnums[0].std::mem::swap. It takes two mutable borrows,&mut max_hereand&mut min_here, and exchanges the values behind them. It avoids a temporary variable.maxandminas methods.nums[i].max(max_here * nums[i])callsmaxon ani32that was read from the vector; becausei32isCopy, readingnums[i]doesn't move anything.- Range.
1..nums.len()excludes the end, soiis a valid index. For a one-element vector the range is empty, and the function returnsnums[0]. - Overflow. The lesson promises that every subarray's product fits in 32 bits.
max_hereandmin_hereare subarray products too, so the multiplications stay within that. Without that guarantee, an overflow in a build with optimizations would wrap silently, and in a debug build it would panic.
Complexity
The loop body does a fixed number of comparisons and multiplications, and nothing grows with the input except the loop count.
Time: O(n). One pass, with a constant amount of work per element.
Space: O(1). Three integers, whatever the length of nums.
Edge cases and common mistakes
- A single negative element.
[-3]gives -3. That is whyresultstarts atnums[0]and not at 0: a subarray must have at least one element. - Zeros.
[0]gives 0, and[0, 2]gives 2. A 0 makes both running products 0, and the next element starts fresh. - Two negatives cancel.
[-1, -1]gives 1, and[-2, -3, -4]gives 12, from the last two elements. - A zero between negatives.
[-2, 0, -1]gives 0, not 2, because the 0 splits the array. - Tracking only the maximum. Without
min_here, the code can't use a negative product that a later negative number turns into the best one. In[-2, 3, -4]the answer needs the -6 thatmin_hereholds at the second element. - Multiplying before swapping. The swap must come before the two updates. Multiplying first would use the wrong value for each.
- Starting at 0 or 1. It gives wrong answers for all-negative inputs such as
[-3]. - More examples.
[2, -5, -2, -4, 3]gives 24, and[1, 0, -1, 2, -3]gives 6.
Testing
[2, 3, -2, 4]gives 6.[-2, 0, -1]gives 0.[-2, 3, -4]gives 24.[-3]gives -3.[0]gives 0.[-2, -3, -4]gives 12.[2, -5, -2, -4, 3]gives 24.[-1, -1]gives 1.[0, 2]gives 2.[1, 0, -1, 2, -3]gives 6.
