Blind 75.06 - Maximum Product Subarray
Maximum product subarray.
Problem description
Given an integer array nums
, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 *
\(10^4\)-10 <= nums[i] <= 10
- The product of any prefix or suffix of
nums
is guaranteed to fit in a 32-bit integer.
Solution type
Caching.
Solution
The \(O(n^2)\) brute force solution is similar to maximum sum subarray; starting at each element, consider each subarray. The efficient solution is also similar, although you don’t specify whether or not to restart the window on every single step. Breaking that down a little more:
The easiest \(O(n)\) solution is a slightly modified Kadane’s algorithm where you don’t set currentProduct = max(elt, currentProduct * elt)
each time. This change is necessary because when you multiply by a negative number, you might be able to multiply by another negative number and flip back to a higher number.
You also need to do two passes instead of one, with one pass going front to back and one pass going back to front. This is necessary because you have “chunks” that start with negative numbers, and you can define these chunks differently depending on whether you’re going forward or going backward.
I did a live commentary sort of thing below with my solutions. The chunk idea is explained after the first iteration in my solution (which didn’t work because it did one pass and didn’t consider the chunk idea).
This requires a different solution than Kadane’s algorithm because we can very quickly “flip” back and forth with negative numbers. For example, in [1,-2,3,-4]
just copy-pasting Kadane’s would give us 3 instead of 24 because it wouldn’t recognize that -4 comes later and flips the sign back when we multiplied earlier by -2.
First thought is to separately track absolute value and sign. When we get to a 0, reset. 10 minutes in I don’t think it’s actually necessary to do that; this is my solution so far.
int maxProduct(vector<int>& nums) {
int globalMaxProduct = nums[0], currentProduct = 1;
// , currentSign = 1;
for (int elt : nums) {
if (elt == 0) {
globalMaxProduct = max(globalMaxProduct, max(currentProduct, elt));
currentProduct = 1;
}
// else if (elt < 0) {
// }
else {
currentProduct *= elt;
globalMaxProduct = max(globalMaxProduct, currentProduct);
}
}
return globalMaxProduct;
}
Fails on [1,-2,3,-4,5,-6]
because it doesn’t consider that including -6
would be better than including -2
. We are biased towards the front instead of considering the back.
Consider the case without any 0s. If you think about it, the entire array has an even number of negative numbers or an odd number of negative numbers. If you have an even number of negatives, then you should just return the product of the whole array (guaranteed to be positive). For an odd number of negative numbers, you can think of there being “chunks” that each start at a negative number. In the case of [1,-2,3,-4,5,-6]
, the chunks going from left to right are [1]
, [-2,3]
, [-4,5]
, and [-6]
. Going from right to left, they go [-6,5]
, [-4,3]
, and [-2,1]
. To find the correct solution, you need to multiply together an even number of contiguous chunks either going left to right or right to left.
You could argue there’s an edge case here where the maximum product is in a single chunk without any negative numbers, e.g. [10,-2,1,-2,1,-2]
, but technically [10]
by itself includes zero chunks with negative numbers, which fits. That just means “chunk” should be defined a little more rigorously :)
I don’t think you need to make additional considerations for elements with value 0, because having 0 in nums
essentially splits the problem into subproblems on smaller subarrays.
Just kidding, needed to handle the edge case where we have multiple 0s in a row (cannot naively max with currentProduct = 1
) or have 0 at front or end (cannot naively initalize currentProduct = 1
).
Final solution after 30 minutes:
int maxProduct(vector<int>& nums) {
int globalMaxProduct = nums[0], currentProduct = nums[0] == 0 ? 0 : 1;
// , currentSign = 1;
for (int i = 0; i < nums.size(); ++i) {
int elt = nums[i];
if (elt == 0) {
globalMaxProduct = max(globalMaxProduct, max(currentProduct, elt));
currentProduct = i == nums.size() - 1 || nums[i + 1] != 0 ? 1 : 0;
}
else {
currentProduct *= elt;
globalMaxProduct = max(globalMaxProduct, currentProduct);
}
}
// repeat going backwards
currentProduct = nums.back() == 0 ? 0 : 1;
for (int i = nums.size() - 1; i >= 0; --i) {
int elt = nums[i];
if (elt == 0) {
globalMaxProduct = max(globalMaxProduct, max(currentProduct, elt));
currentProduct = i == 0 || nums[i - 1] != 0 ? 1 : 0;
}
else {
currentProduct *= elt;
globalMaxProduct = max(globalMaxProduct, currentProduct);
}
}
return globalMaxProduct;
}
Not the prettiest code, but the reasoning is sound and it’s actually pretty darn effective (90th percentile in speed and 80th percentile in mem).
I have a passing submission from 2.5 years ago (which to be clear I did not remember) that looks like this:
int maxProduct(vector<int>& nums) {
int maxP = nums.front();
int curr = 1;
for (int i = 0; i < nums.size(); ++i) {
// if (nums[i] == 0) {
// maxP = max(maxP, 0);
// curr = 1;
// int j = i - 1;
// while (j >= 0 && nums[j] > 0) {
// curr *= nums[j];
// maxP = max(maxP, curr);
// }
// }
// else {
curr *= nums[i];
maxP = max(maxP, curr);
if (curr == 0) {
curr = 1;
}
// }
}
// // back is also a 0
// curr = 1;
// int j = nums.size() - 1;
// while (j >= 0 && nums[j] > 0) {
// curr *= nums[j--];
// maxP = max(maxP, curr);
// }
curr = 1;
for (int j = nums.size() - 1; j >= 0; --j) {
curr *= nums[j];
maxP = max(maxP, curr);
if (curr == 0) {
curr = 1;
}
}
return maxP;
}
This is actually a nicer looking solution because it doesn’t have as much special casing for 0-value elements. It makes perfect sense too; instead of resetting, just multiply by the current element (you also avoid the edge case where the next element is 0). It’s interesting to see this reflected in the commented-out code; I did have the extra conditional blocks, but cut them out after realizing that I could just multiply by the current.
I suppose I was a decently smart cookie back then. Heh.
It is in fact possible to do only one pass. Taking a glance at some of the other solutions, it seems like what you could do is track both a running max and running min and just recalculate / swap them when you encounter a negative. This is quite nice.
Leave a comment
Your email address will not be published. Required fields are marked. *