Maximum Product Subarray
- 2 min read
- LC-Medium
3 years ago
Solution
- Not your typical dynamic programming problem-- you're not having any dp array or anything
- This is kinda similar to Kadane's Algorithm, but a little different because a number can turn from negative to positive anytime
- In Kadane, we would reset to 0 whenever a new low was seen to imitate ignoring the subarray that came before
- Here instead, we keep track of two numbers, the current minimum and current maximum subarray product seen so far
- This lets us be flexible in that we can turn the current subarray sum to negative or positive anytime
- Remember in Kadane, we either used the current number, 0, or current subarray sum -> between 3 choices
- Here, we would either use the current subarray max product * num, or current subarray min product * num, or just num itself
- We need to keep track of both max and min because a negative can turn into positive anytime
- ZEROES ARE AUTOMATICALLY TAKEN CARE OF!!
- If still confused, read the editorial!!
From the editorial:
Let's see this problem as a problem of getting the highest combo chain. The way combo chains work is that they build on top of the previous combo chains that you have acquired. The simplest case is when the numbers in nums are all positive numbers. In that case, you would only need to keep on multiplying the accumulated result to get a bigger and bigger combo chain as you progress.
However, two things can disrupt your combo chain:
- Zeros
- Negative numbers
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def maxProduct(self, nums: List[int]) -> int:
ans = max(nums)
cur_min, cur_max = 1, 1
for num in nums:
tmp = cur_max * num
cur_max = max(cur_max * num, cur_min * num, num)
cur_min = min(tmp, cur_min * num, num)
ans = max(ans, cur_max)
return ans