Others - Maximum Product Subarray
All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.
Difficulty : Easy
DP
Problem
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:
1
2
3
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
1
2
3
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Solution
It’s evident that we can solve the problem just by traversing the array one time, but the only problem is the - sign which will shift the result. The - sign will reverse the result, that is, it will change the largest product to smallest one and the smallest one to largest one. Since we won’t have any control over it, why don’t we track both and finally find out the max one.
So let’s create two variables smallest and largest. We need to set them to 1 and not 0 since we are working with product here.
1
smallest, largest = 1, 1
We also need to keep track of the largest at every iteration as in case there is only one negative number then at the end of the loop the largest value may not be largest. Try to solve [2,3,-2,4] and you will see at the end the largest is 4, however the correct result is 2 x 3 = 6 and not 4.
The other important trick to understand which value to initialize this with ? We know that the nums array can have any number, positives or negatives.
Say there is just one number and that is negative [-5] then the max_product must be -5. So we can initially say, the max(nums) is the max_product without knowing anything about the nums array.
1
max_product = max(nums)
Now, please refer the diagram below. Here we are going to keep track of min and max product for every iteration of the loop. We need to compare 3 values.
MAX = max ( largest*nums[i],smallest*nums[i], nums[i])MIN = max ( largest*nums[i],smallest*nums[i], nums[i])
We need to consider the current value (nums[i]) as well for finding MIN and MAX. Notice above we have -2 as max and -12 as min. Now 4 could be the next MAX and not -8.
1
2
3
4
5
6
for i in range(len(nums)):
MAX = max ( largest*nums[i],smallest*nums[i], nums[i])
MIN = min ( largest*nums[i],smallest*nums[i], nums[i])
largest = MAX
smallest = MIN
max_product= max(max_product,largest)
We have one more edge case to take care. Whenever nums[i]==0 we need to reset largest and smallest otherwise all the products going forward will be 0.
1
2
3
4
5
6
for i in range(len(nums)):
if nums[i] ==0:
largest=1
smallest=1
continue
MAX = max( .... )
Finally just return the max_product.
1
return max_product
Final Code
Here is the full code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def max_product(nums):
smallest, largest = 1, 1
max_product = max(nums)
for i in range(len(nums)):
if nums[i] ==0:
largest=1
smallest=1
continue
MAX = max ( largest*nums[i],smallest*nums[i], nums[i])
MIN = min ( largest*nums[i],smallest*nums[i], nums[i])
largest = MAX
smallest = MIN
max_product= max(max_product,largest)
return max_product