152. Maximum Product Subarray
Description
https://leetcode.com/problems/maximum-product-subarray/
Note: the input array is assumed to have at least one element.
Solution
This is similar to the maximum subarray problem, which can be solved using Kadane's Algorithm. We can use what we learned from that problem and apply it here.
Because this question asks for the product, negative numbers have a different effect. A subarray may flip in and out of the solution as negative numbers are included.
As with the maximum sum subarray, we will keep track of the current and max product. But we will need to keep track of the minimum product too. This is because a negative product may become positive if we encounter another negative number.
Examples
Given an input of: [5, 3, -1, 2, -2, -3, 6]
5
5
[5]
5
[5]
5
[5]
3
15
[5,3]
3
[3]
15
[5,3]
-1
-1
[-1]
-15
[5,3,-1]
15
[5,3]
2
2 [2]
-30
[5,3,-1,2]
15
[5,3]
-2
60
[5, 3, -1, 2, -2]
-4
[2, -2]
60
[5, 3, -1, 2, -2]
-3
12
[2, -2, -3]
-180
[5, 3, -1, 2, -2, -3]
60
[5, 3, -1, 2, -2]
6
72
[2, -2, -3, -6]
-1080
[5, 3, -1, 2, -2, -3, 6]
72
[2, -2, -3, -6]
Given an input of [3, 2, 0, 5, 6, -1]
3
3
[3]
3
[3]
3
[3]
2
6
[3, 2]
2
[2]
6
[3,2]
0
0
[0]
0
[0]
6
[3,2]
5
5
[5]
0
[0, 5]
6
[3,2]
6
30
[5,6]
0
[0, 5, 6]
30
[5,6]
-1
0
[0, 5, 6, -1]
-30
[5, 6, -1]
30
[5, 6]
class Solution:
def maxProduct(self, nums: List[int]) -> int:
# since nums is guaranteed to be not empty, initialize the variables to the first element
current_product = nums[0]
max_product = nums[0]
min_product = nums[0]
for i in range(1, len(nums)):
# The current_product is calculated at line 13. However, we need to use the current_product in the min_product calculation.
# So we need to store the prev_current_product so that value can be used in the min_product calculation
prev_current_product = current_product
# This is like Kadane's algorithm where we take the max of either the current_product * the element, or the element.
# But now that we have a min_product as well, that value needs to be included too.
current_product = max(min_product * nums[i], current_product * nums[i], nums[i])
# Use Kadane like algorithm for the min_product too. Notice we are using the prev_current_product and not the current_product just
# calculated above.
min_product = min(min_product * nums[i], prev_current_product * nums[i], nums[i])
max_product = max(max_product, current_product)
return max_productLast updated