Leetcode — 152. Maximum Product Subarray

The link to the problem: https://leetcode.com/problems/maximum-product-subarray/

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Thoughts:

The problem is pretty similar to this problem — 53. Maximum Subarray on Leetcode. I also wrote a story explaining how we can solve it in O(n) time.

In problem 53, we are asked to find the maximum sum of the contiguous subarray. The strategy we used is that we use a variable temp to record the maximum sum we can get if the contiguous subarray ends at the current position. We will add the current number nums[i] to the temp variable if we can extend the current contiguous subarray and increase the sum. If we found that the value of nums[i] alone will bigger than it adds on the current contiguous subarray, we will stop extending the subarray and let nums[i] be the new head of our current contiguous subarray.

However, we cannot use the same strategy in this question. Maybe at this point, the “temp” variable that records the product of the current subarray times the current number cannot increase the current product and we just decide to end the current contiguous subarray and start a new one. However, it is possible that if we keep extending the current subarray until we meet the next negative number, the product of the current subarray then will be the maximum product of the whole array.

Since this question is asking product, as long as we haven’t meet any 0 to “crash” everything, the ABSOLUTE VALUE of the product is always bigger and bigger when the current contiguous subarray is longer.

Code Logic:

Although we cannot use exactly the same strategy of how we solve problem 52 to solve this problem, we can still use some additional variables to help us solve this problem in O(n) time complexity.

The idea is that instead of only use one temp variable to control the product of the current contiguous subarray, we use 2 variables to help us to solve the problem:

  1. min: will always hold the minimum product we can get from the current contiguous subarray
  2. max: will always hold the maximum product we can get from the current contiguous subarray

⚠️It is guaranteed that min and max represent the minimum and maximum product when the contiguous subarray ends in the current position(i.e., nums[i]).

The reason why we keep two product variables is that we will swap min and max if nums[i] is a negative number. Since if nums[i] is negative, we will form a new min value from the product of nums[i] and the current maximum value and vice versa.

👷Let’s see an example if we have an input like [3,4,-5,10,2,-3]:
(We will use rst variable to store the final answer.)

⚠️Note that we won’t know what’s the length or what elements inside the current subarray that forms the maximum or minimum product, we only know it includes the number of the current position. However, in the below example, I will still present what forms the current subarray for better understanding.

🔧Step 0. Initial State of min and max variable. We will assume we can get the minimum and maximum product from the subarray that only contains the first number of the array.
Our final answer variable rst will also be set to the value of the max variable.

Initial State

🔧Step 1. When the current position is at 1, the current number is 4. We simply update the min and max variable we can get when the subarray ends in nums[1]. (i.e., extends the current subarray)

step 1 result

💭rst is 12 since we find a bigger maximum product.

🔧Step 2. When the current position is at 2, the current number is -5. This time, we first swap the value of min and max since we will get a bigger product if we multiply the current value with the min number and vice versa.

step 2 result

🔧Step 3. When the current position is at 3, the current number is 10. We simply update the min and max variable we can get when the subarray ends in nums[3].

step 3 result

🔧Step 4. When the current position is at 4, the current number is 2. We simply update the min and max variable we can get when the subarray ends in nums[4]. (i.e., extends the current subarray)

step 4 result

💭rst is 20 since we find a bigger maximum product.

🔧Step 5. When the current position is at 5, the current number is -3. Again, we swap the value of min and max since we will get a bigger product if we multiply the current value with the min number and vice versa.

step 5 result

💭rst is 3600 since we find a bigger maximum product.

🚧We end traversing the whole array and we will just return what we have in the rst variable.

Below is the 1ms code that beats 94% —

public int maxProduct(int[] nums) {
int n = nums.length;
int rst = nums[0];
int max = rst, min = rst;
for(int i=1;i<n;i++)
{
int cur = nums[i];
if(cur<0)//swap max and min
{
int temp = max;
max = min;
min = temp;
}
min = Math.min(cur*min, cur);
max = Math.max(cur*max, cur);
rst = Math.max(max, rst);
}
return rst;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store