Maximum Product Subarray - Dynamic Programming - Leetcode 152

0:00 - Brute Force
2:00 - Drawing optimal Solution
10:00 - Coding solution

leetcode 152

#product #subarray #python

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[CostaKazistov]

Highly underrated channel.
You deserve 10x the number of subscribers.

Clearest explanation style of Leetcode that I have come across yet - on par with Tech Dose and Back to Back SWE channels.

Python is also a great choice for these videos, easy to understand, even though I only code in C#

[edmonddantes]

yeaaaah no chance I come up with this on the fly in an interview situation. Guess I'll have to memorise as many approaches as possible

[fahim]

The explanation is very good. However the test case have changed over the past 3 year. If i run this code in (c++) I get a "runtime error: signed integer overflow" for the input of "nums =
[0, 10, 10, 10, 10, 10, 10, 10, 10, 10, -10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 0]".

[Sjejdbangdw]

Another way to think about it, perhaps more intuitive to some, is that we divide the array into segments that are separated by 0s (or consecutive 0s). Then, the total product of each segment is gonna be the largest for this segment unless its negative. In that case, we just divide it with the first negative product in the segment(to get a positive product) if possible.

[polyrain]

Hey, genuinely you're one of the best channels for this I've ever found. Thank you so much!

[DanhWasHere]

I love that you didn't mention Kadane's Algorithm so we don't get hung up on the terminology of "Max Product Subarray" => apply Kadane's and instead just understand the logic. E.g. A lot of YoutTube videos are titled how to apply Kadane's Algorithm instead of the type of problem it is used for, which is the more important information.

[superchetube]

Hard to imagine a company ask this question during the interview.
I don't know if anyone can come up with the solution in a few mins if never meet this problem before.

[camoenv]

A fun trick I like to use is to initialize curMin, curMax, and result to the first number of the array, then iterate over all elements of the array except for the first. Then we don't need to run a max operation to determine the initial result.

Also, if you do the new curMax and curMin calculations on a single line, you can avoid using a tmp var. (The entirety of the right side of the equals sign is evaluated before the newly computed values are assigned to the vars

def maxProduct(self, nums: List[int]) -> int:
curmax = curmin = res = nums[0]
for num in nums[1:]:
# remember to include num, so we can reset when a 0 is encountered
curmax, curmin = max(curmax * num, curmin * num, num), min(curmax * num, curmin * num, num)
res = max(res, curmax)
return res

[sliverofshadows]

Great video. The catch of the question seems to be in knowing that we need to also track the minimum _in addition_ to the maximum, but I have some trouble understanding how we could manage to figure that out. Of course, once the answer is given, the whole solution makes sense, but when I was trying to do this question on my own, the thought of tracking the minimum never even occurred to me.

Any tips on how to go about warping your thought process to think about that as well?

[vimalslab]

for c++ coders ...
you can compare three values in max fn by using {}.
eg. maxVal= max({a, b, c});

[saibharadwajvedula]

basically having n in max/min of (n*max, n*min, n) helped us sailing across the edge case of 0.

[Zero-bgvr]

I'm in awe, the way he explained it. Well done buddy. Explained a tough concept so easily.

[robertsedgewick]

Best explanation on youtube. Systematic and intuitive. Thanks for sharing!

[andrewmelnikov]

that is clearest, coherent, and most understandable explanation I have ever met.

[abbyjon]

Your channel is so underrated man. Thank you for doing this. I wish we had a professor like you in my college.

[dorondavid]

For your code, in your optimal solution section, you use an example of [-1, -2, -3], and then say the max is 2 and the min is -2
I don't think your algorithm will work if the array was [-2, -1, -3].

The min and max would be the same, but it wouldn't be a CONTIGUOUS subarray answer then.

Please correct me if I'm wrong!


Edit: Actually the code makes sense when I look at it because you take the min of THREE items.
From the description part it sounded like you were just taking the min/max and that's it

[visalearn]

Amazing video, I like the way you explain things. Kudos.

Just want to point out that res = max(nums) at the beginning is not needed if you remove the if (n ==0) check. max function would need to iterate the entire array to find out the max. If the array is huge, this will take significant amount of time.

[tuanp]

So far, your series has been great thank you. Please elaborate more on the section “drawing the optimal solution”. If the array was [-2, -1, -3, 4] the max product should be 12. However, following your min, max strategy it computes to 24

[smrutiranjansahoo]

Thank you! I just want to make a small suggestion. We can initialize the result with the first element of the input array. It will simplify the solution further.

[THEAVISTER]

Honestly, the best explanations I have seen. Thank you so much, your doing an amazing job 👊🏽👊🏽👊🏽