Maximum Product Subarray - Dynamic Programming - Leetcode 152

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@abhinav4095]

thank you

[@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#

[@jude3926]

channel isn't underrated ngl

[@jean4j_]

@@jude3926 Underrated I guess compared to those popular "programming" channels which are basically just "entertainment"

[@edmonddantes587]

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

[@rebornreaper194]

Yeah it's BS

[@xaenonch.8250]

Lmao I feel the same

[@beginner6667]

@@rebornreaper194what is BS

[@rebornreaper194]

@@beginner6667 the premise

[@shravani2922]

@@beginner6667 bull sh*t

[@polyrain]

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

[@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.

[@yagniktalaviya2146]

i did

[@harsh9558]

@@yagniktalaviya2146 wow R u a competitive coder?

[@yagniktalaviya2146]

@@harsh9558 trying it out!

[@vallabhchugh2075]

@@yagniktalaviya2146 amazing

[@abhijit-sarkar]

@@yagniktalaviya2146 Good job man, I always believe whatever some random guy says on the internet.

[@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.

[@TheDSasterX]

I hate random Jargon. "Kadane" doesn't tell me anything.

[@leeroymlg4692]

it's probably best that these problems aren't taught to use some algorithm named after a person. Because how many people actually have every single algorithm someone else came up with memorized?

[@sliverofshadows475]

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?

[@protyaybanerjee5051]

Haha! Same question, but the answer is invariably "Solve more problems" . I think that it's pretty tough to come up with this solution in an interview setting, unless you have practised similar problems.

[@Majitsu]

most people that make these videos dont come up with the answers themselves so they cant explain how they got to it.

[@rodion988]

You get to this idea when you think about edge cases and realize that you don't know how many negative values there are. 0 : You have to reset your current product at each 0 and treat the rest as a new array. Negative value: makes your prior results negative. Will make the sum positive only if after it another negative value is encountered and there was no 0 in-between. So after encountering a negative value you always have 2 paths you can follow and you don't know which one will turn out to be bigger. But the negative value multiplied with positive numbers will become only smaller... Which is good: the negative value grows but in a different direction. So we have to take min() of it.. it allows the current negative result to grow into negative direction as max() allows current positive result to grow into positive direction. The next time we encounter second negative and multiply the current negative (min) result with it, it will turn out to be a bigger positive value than what we had in the current positive result variable.

[@alexcuenca]

Many of these problems have tricks that it's very unlikely one can figure out. But don't worry, it doesn't mean much really. I'd bet this is the case for everyone given a significant amount of problems. You just have to check the solutions in these problems a lot of the times. Everybody does it. Whoever says they don't, be suspicious lol.

[@merrygamer236]

@@rodion988 Thanks, this helped me understand the logic better.

[@mostinho7]

6:20 this is same as kadane’s algorithm for maximum subarray, where we keep track of max subarray ending at ith index. For this problem since two negatives multiplied together give a positive, we need to keep track of the min subarray ending at ith index AND max subarray ending at ith index. Then for i+1 position, if it’s a negative value, then the max product subarray ending at i+1 position is that value * min subarray ending at ith position (if it’s negative value) Dealing with 0s as elements, the zero resets our min and max subarray ending at 0 element’s index. So both min and max become 1 after encountering 0

[@vimalslab3398]

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

[@khangpiano549]

Thanks!

[@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.

[@challengemania4447]

yes correct.. We can use dequeue data structure

[@andrewmelnikov3102]

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

[@camoenv3272]

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

[@tearinupthec0astline]

Remember that slicing nums[1:] is an O(n) operation, so it’s not actually saving any time over using max at the beginning. If we want to avoid that altogether we can just start res as float(‘-inf’) and curmax = curmin = 0

[@Grawlix99]

@@tearinupthec0astline True, but we could also just use a range-based for loop and start from index 1.

[@rm0ndo]

To add to this, only res needs to be initialized to the first array element, min and max can stay as 1

[@TarunKumar-qs9dj]

@@tearinupthec0astline we can use For i in range(1,len(nums)): num=nums[i] Now this won't be a problem

[@mastermax7777]

I think code readability is more important compared to the slight (if any) benefit in performance from doing this trick. Its still o(n), its not going to matter much

[@saibharadwajvedula6793]

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

[@ChrisCox-wv7oo]

yup yup.

[@geekydanish5990]

not only that it also helps in keeping the product of contiguous subarray (having 3 params in max and min function)

[@robertsedgewick1266]

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

[@Zero-bg2vr]

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

[@marchanselthomas]

me too

[@dorondavid4698]

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

[@noumaaaan]

I swear i was just thinking about this and hoping someone else noticed. Can you please explain how it works, since it's not contigious.

[@mynk_rjpt]

dagg gai

[@tarunpahuja3443]

@@noumaaaan they are considering the ith element too. Effectively you have max ending at ith element, min ending at ith element

[@bestmovies36]

​@@noumaaaan I was in the same boat during explanation time but my doubt got clarified after coding. Because here we are considering min and max products till zero value appears.

[@kamsalad]

Still don't really understand this let's say you have an array: [1, 2, 3, 0, 1, 2] The maximum product subarray is 6 If you add one more number you would have something like: [1, 2, 3, 0, 1, 2] [3] Here, the answer is still 6, but shouldn't it be 3*6 = 18, according to the video?

[@abbyjon461]

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

[@ujjawalpanchal]

@NeetCode, you don't need to introduce 1s in the zero condition. It works even without that. Because you are taking a `max(num, curr_max * num, curr_min * num)` so if curr_max * num = 0, max will be num incase of +ve num. Also, for -ve num, you are taking min(num, curr_max * num, curr_min * num)` so for -ve num, if curr_max * num == 0 and curr_min * num == 0, curr_min will be set to num (since num < 0).

[@tanmayagupta4591]

Thanks for explaining.

[@arpitcts]

For values [-2,0] this code returns -2. where as the output should have been 0. so I have made one slight change. I kept the flag to indicate if we found zero. and at the end, if (flag) max(res,0) else return res

[@HanSmellsGood]

output is still 0 with this code

[@ritwikpm]

The res = max(nums) initiation is extremely relevant - Should have a deeper focus on this if they ever remake the video...

[@josuegialis3]

I am so happy and satisfied with the quality of your solutions and thorough explanations. Thank you so much and please keep up the good work!

[@smrutiranjansahoo9161]

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.

[@fahim0404150]

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]".

[@satyendrakumarsharma3513]

The intermediate values would overflow the range of integer. So for better to use a double for these variables, and cast it back to (int) before returning.

[@visa2learn]

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.

[@The9TKitsune]

Additional point of order: min/max don't work on None, so initialize res as `float("-inf")` or -(math.inf)

[@THEAVISTER]

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

[@qwerty6-6]

6:18 How is the minimum product of (-2 and -1 ) = -2 ? Shouldn't the maximum and minimum both be 2 ?

[@joy79419]

[-2] is also a subarray

[@qqqqoeewqwer]

@@joy79419 Thank you!

[@goodtoseeya1543]

Thanks man. Your channel deserves more subs.

[@supreethvasisht2451]

i found the procedure super complicated! Didn't understand why this method solves the problem.

[@tuanp01]

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

[@tuanp01]

@NeetCode

[@yadwindersingh806]

for n = -2, we get max = -2, min = -2, maximum product = -2 for n = -1, max = -2, min = -2, we get max = 2, min = -1, maximum product = 2 for n = -3, max = 2, min = -1, we get max = 3, min = -6, maximum product = 3 for n = 4, max = 3, min = -6, we get max = 12, min = -24 maximum product = 12

[@xingdi986]

since minimal/maximal number times the negative/positive number could both achieve the maximum product, you need to note down both minimal and maximal. Do I understand correctly?

[@j.franciscox3318]

8:06 for example [-2, -1, -3] [-2, -1] -> min=-2, max=2 [-2, -1, -3] -> can't get max = -2 x -3 = 6.

[@thevagabond85yt]

It's not contiguous

[@AliBazilov]

Hi, thank you for great explanation! Btw, time complexity of brute force is O(N^3). It can be optimized to O(N^2)

[@TheMadRunner00]

I was looking that someone would point this.

[@empowercode]

Hey! I just found your channel and subscribed, love what you're doing! Particularly, I like how clear and detailed your explanations are as well as the depth of knowledge you have surrounding the topic! Since I run a tech education channel as well, I love to see fellow Content Creators sharing, educating, and inspiring a large global audience. I wish you the best of luck on your KZbin Journey, can't wait to see you succeed! Your content really stands out and you've obviously put so much thought into your videos! Cheers, happy holidays, and keep up the great work :)

[@crossvalidation1040]

Nice explanation! To work in leetcode submission: curMax = max(curMax * n, n, curMin * n) curMin = min(tmp, n, curMin * n)

[@mastermax7777]

Can you explain why this version works in leetcode but not what he wrote in the video? whats the difference

[@hwang1607]

this is a crazy solution could not have thought of it

[@RandomShowerThoughts]

this guy is leaps better than everyone else on youtube

[@anonymoussloth6687]

CPP Solution: int Solution::maxProduct(const vector &A) { int mx = 1, mn = 1; int ans = INT_MIN; for(auto& x : A) { if(x < 0) swap(mx, mn); mx = max(mx*x, x); mn = min(mn*x, x); ans = max(ans, mx); } return ans; }

[@abdosoliman]

I went with a slightly different approach I divided it into a map of ranges and their product. So basically I start at a value keep multiplying until I see a zero then I use the start,end indecies as map keys and the value is the product. After constructing the map then it's simple you make a for loop that keeps dividing until it hits the first negative number. Another for loop keeps dividing from the back till hits the last negative or the first negative from the back. We compare and update the max_product. My solution is practically the a single pass but I would prefer your solution because it's less code and easier to understand.

[@AlexN2022]

a conceptually simpler approach: For any *r* boundary we want to include either the whole [0:r] if *curr* is positive, or (l:r] if not, where *l* is the index of the first negative element in nums. Rational: we want to include as many numbers as we can as long as we have an even number of negatives. So we calculate a *blob* that is the first negative product. Then at each step we compare the running *max* with either *curr* or *curr/blob* if *curr* is positive/negative respectfully. One last step is to reset *l* when we encounter a 0, because otherwise any sub-array that includes a 0 will produce 0. To do that we set blob back to original 1.

[@pakkunhatake]

Solid video, just a small correction. For the DP part, we are actually finding the min/max of the subarray ending in the ith index. So once we reach the end, it's not necessarily that the last element has to be included in this max subarray. But by the end we would have already encountered the max subarray as we were processing and saved it already in our return variable. Another way to think about is that if we had two arrays dpMin and dpMax, both of length N, which represent the min and max of subarray ending at ith index. We use both of these in our computation. And then at the end of our algorithm we can return max(dpMax). The reason we can do away with these arrays is that we only look back one index, i.e., we only look at dpMin[i-1] and dpMax[i-1], so removing the arrays is an optimization in and of itself

[@mrigankanath7337]

THis is a gem of a channel; Nice work dude

[@joshuabump6147]

My main struggle with the problems in these technical interviews is finding solutions not requiring O(n squared).

[@shashankgarg7476]

Amazing channel found today, shoot up to 1 million soon!!

[@sasirekhamsvl9504]

Very well explained. I loved it. Too good explanation. I have subscribed and liked. Keep making more videos. Awesome work really.

[@yidatong443]

How about -2, -1, -3? For (-2, -1) max-> 2, min->-2. Then for (-2, -1, -3) max->-3*-2 = 6, min ->-3*2=-6. But (-2, -1, -3) max->[-1, -3] = 3 min->[-2, -1, -3]=-6

[@amitmahato4876]

Yeh the answer is 3, as the maximum is 3 overall

[@arnobpl]

Great explanation! We can refactor the code for even better readability: ``` def maxProduct(self, nums: List[int]) -> int: product = nums[0] maxx, minn = product, product for x in nums[1:]: newMaxx = max(x, maxx*x, minn*x) newMinn = min(x, maxx*x, minn*x) maxx = newMaxx minn = newMinn product = max(product, maxx) return product ```

[@seanculloden]

You have to ask at each point in the array as you move through what the greatest and smallest product is or the value at the index itself. If the answer is that the value at the index is the most negative or the most positive we are removing from consideration the past values in our result subarray. Consider the following example. [2, -5, -2, -4, 3] at each index figure out the min and max subarray at that point index 0: min: 2 = [2] max: 2 = [2] (our only choice is 2 since we are at the beginning) index 1: min: -10 = [2,-5] max: -5 = [-5] (reset max) our choices ([2, -5], [-5]) index 2: min: -2 = [-2] (reset min) max: 20 = [2,-5,-2] our choices ([2,-5,-2], [-5,-2], [-2]) index 3: min: -80 = [2,-5,-2,-4] max: 8 = [-2,-4] our choices ([2,-5,-2,-4], [-2,-4], [-4]) index 4: min: -240 = [-2,-5,-2,-4,3] max: 24 = [-2,-4,3] our choices ([2,-5,-2,-4,3], [-2,-4,3], [3]) result 24 = [-2,-4,3]

[@beyzayildirim0]

Thanks for the explanation! I think you can do curMax, curMin = max(n * curMax, n * curMin, n), min(n * curMax, n * curMin, n) if you dont want to have a temp value

[@braedenlewis6009]

I just asked this same question XD I wasn't sure if it would work that way or not

[@kahlilkahlil9172]

How does the usage of min will work as this is a contigous subarray ? for example if the array is [-2, -1, -3] then the max of sub [-2, -1] is 2 while the min is -2, if we try to get -3 * -2 this is wrong, because it become a non-contigous array.

[@kahlilkahlil9172]

Anybody can help whether I am misunderstood something of the problem / solution being explained ?

[@VignetteQ]

@@kahlilkahlil9172 Late response but the reason that doesn't happen is in the line that sets curMin = min(..., curMin * n, ...). In your example curMin would have the value of -1 when n = -3, not -2; curMin will always be updated with each n. Your example would occur if the min() calculation had not curMin * n, but just curMin.

[@ravijha4965]

if input is with only [0] and without that assignment line of res = max(nums), how can we save this time here removing this line ?

[@vivivi5678]

When i tried this solution in java, i got an error for one of the testcases due to integer range issue. I changed it to double and it worked.

[@vroomerlifts]

Same, was searching for this

[@visiedo72]

Sorry, but this solution wouldn’t work for input arrays where all values are negative or 0, would it? Eg for [-2, 0, -1] it would yield -1 as the result, right?

[@chanakyakenguva3795]

No, as he has taken res = max(nums) in line no 3, the res would be set to 0 when all values are negative or 0

[@sharad3877]

watching your first video and subscribed.So clear and beautiful explanation❤❤

[@vanillatrivedi]

For the input array {-2,0,-1} , I was getting the result as -1 instead of 0. i believe when we 're resetting the min/max value as 1 we need to reset the maxsub to it;s default.

[@ir2001]

Solution: Check whether the input array contains a zero (for example, use a flag variable and update it before "continue" when you encounter a 0). Then, if "res" comes out to be a negative integer when it has been found that the input array contains a 0, the maximum product would indeed be zero (the edge case that you rightly pointed out); otherwise, "res" is correct. if (res < 0 and zeroPresent) { return 0; } return res;

[@MrHunty]

What I did that helped this issue, was inside the if statement, I added a clause that "result = Math.max(result, 0)" which checks to see if 0 is bigger than what is the current max. It passed all of leetcodes tests, so I'm assuming it's okay?

[@pankajupreti8967]

just remove arr[0]=0

[@sushmitgaur8537]

6:03 i don't understand this part. why?

[@DavidDLee]

I think the genius in the solution is not fully explained. The difficulty in this question is how to avoid segmenting the input or doing two-pointer type approaches to handle negative numbers and zeros. It is not immediately obvious that you can multiply the current max of previous values with the cell's value, n, and get a valid result, or that you can add 'n' to the max() / min() to skip zeros and negative numbers.

[@mohamedgabr5623]

Dude, you are a GREAT teacher!! I wish I had you in my DSA class 🤣

[@aseemsameer7281]

Mostly the questions require returning a subarray that contains maximum product. Here, with all the cases considered by you, we need a storage of numbers in the array and their product till nth position, and continuing from those to add new elements. For such purposes, dynamic programming becomes more complex. Is there any simpler solution to this?

[@anshab16]

so simple so elegant so beautiful

[@ch33ze0g]

I'm not understanding how at 6:03, the min could be -2. Isn't it just 2?

[@omartahboub2900]

Thanks!

[@NeetCode]

Thank you so much!

[@patrickadjei9676]

At first I was like... it might still do 1*2*4 = 8 although the answer is 4. But after printing it out, I was like wow... nice work.

[@bujagawnisaitejagoud2461]

Instead of resetting every time when you find 0 in the array. We can also use the element of array in comparison while deriving max and min at each level. class Solution { public int maxProduct(int[] nums) { int n = nums.length, maxProd = nums[0], minProd = nums[0], res = nums[0]; for(int i=1;i

[@stith_pragya]

Thank You So Much NeetCode Brother................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@tejeshvaish17]

awesome man , you have a soothing voice

[@optimistic_dipak8632]

Great video... Actually, we do need that if condition inside for-loop to handle the following kind of inputs: nums = [-2,0,-1]

[@ananthrajsingh6787]

Nope, that condition will mess up this test case. There should be no if condition. If we have the if condition, the result of your test case will be 1, not 0

[@chiranjeevipippalla]

You made a very scary problem look easy. Thank you

[@markolainovic]

I feel like this is not a dynamic programming problem; it seems to me that it's not true that we look at the solutions of previous sub-problems and then use them directly to calculate the bigger sub-problem solution. Case in point: [4 5 6 -1 2 3] Let's say we came to the very last step, i.e. we have our min/max for the array [4 5 6 -1 2] and then we need to use that with 3. If this were the dynamic programming problem, you could say, well, I know the biggest sub-array product for [4 5 6 -1 2] and then I need to use it somehow with 3. But it wouldn't work. The biggest product for [4 5 6 -1 2] is 120, however, there's a gap between [4 5 6] and 3. It would be a mistake to just multiply 120 by 3. Instead, what we're doing is, we're kinda having this "rolling window" effect -- we are looking at the biggest/smallest sub-array STARTING from the right and going toward the left edge of the sub-array. That's why the code will give us "the current max" for [4 5 6 -1 2] as 2. And none of this would work had we not, at each step, memorized the biggest product we've found so far in `res`. So yeah, I hope my explained my rationale well enough - I don't think this is a usual dynamic programming task where one, at the last step, gets the final result by combining the previous sub-problems' results.

[@justinvilleneuve251]

yep i agree. Optimal substructure doesnt apply here in all cases

[@arunraj2527]

There is another easy solution. Run Kanane's product to get max from left and right, return max. public static int maxProductSubArray(int[] nums) { int max = nums[0]; int temp = 1; for(int i=0;i=0;i--) { temp *= nums[i]; max = Math.max(max,temp); if(temp==0) { temp=1; } } return max; }

[@victoriatfarrell]

Having the 3 arguments for cur_max/cur_min lets you avoid the if statement, as it just resets to the present num if previous calculations have been zero'd.

[@PradeepKumarGontla]

Very good explanation, we can initialize res with nums[0].

[@lemons.3018]

now they have added new test cases which causes the overflow ,

[@kenzhu6040]

So the subproblem is actually the max/min of the current subarray that *includes* the last element. It got me confused for a bit, and I think you should always be clear on what subproblem we're solving in a DP problem.

[@dheepthaaanand3214]

Yes exactly, otherwise we would have the result at curMax of the nth element, but that's not the case so we have to maintain a max result

[@lucaswang8457]

Update: `res = max(nums)` is actually unnecessary. We can safely set `res = nums[0]`.

[@andrewchen3010]

Not true for the implementation LeetCode uses, because of the if statement

[@alviahmed7388]

@NeetCode, I am really bad at identifying patterns like this. What can I do to get better at it? You are good at approaching problems from different angles which is stuggle with

[@sentinel-y8l]

You can avoid the three argument max, min and just use 2 arguments if you swap curMax and curMin when n < 0.

[@natnaelzewdu4289]

setting res to max(nums) adds extra computation that does nothing. curmin, curmax = 1, 1 res = float('-inf') for n in nums: tmp_n_times_max = n*curmax tmp_n_times_min = n*curmin curmax = max(tmp_n_times_max, tmp_n_times_min, n) curmin = min(tmp_n_times_max, tmp_n_times_min, n) res = max(res, curmax) return res

[@axellbrendow1]

It's interesting how currMax and currMin can get weird values during the for loop, but, at the end, the answer is right hahah

[@insaneclutchesyt948]

we dont need to check for zero right because we are taking min, max of three elements in which the nums[i] is also there so it will take the nums[i] , and the currmin currmax will not become 0 for the remaining array ! correct me if im wrong

[@salonidabgar1174]

We'll also have to store the value of currMin till the previous iteration in a temporary variable as we did for storing currMax. This was the only problem with the code. Otherwise, great explanation!

[@AbhishekKumar-ym1pz]

We don't have to store currMin because it is not being used again in the same iteration as currMax is used

[@naveen9102]

i have been wrecking my head with this problem from yesterday , and your explanation is the best i could i ask for

[@NeetCode]

Glad it was helpful!

[@work-v4g]

you may avoid using the tmp variable by: curMax, curMin = max(n * curMax, n * curMin, n), min(n * curMax, n * curMin, n) as in Python: a, b = b + 1, a + 1 -> will do the calculation simultaneously.

[@victoriatfarrell]

Yes, but that does make it noisy to read

[@luisady8990]

My solution in Python: import fileinput # Maximum subarray problem - Find the maximum sum in a continuous subarray. # Kandane's Algorithm def maxSum(nums): if len(nums) == 0: return nums[0] maxValue = minValue = globalMax = nums[0] for i in range(1, len(nums)): # Keep track of local minimum and maximum tempMax = maxValue maxValue = max(nums[i], nums[i]*maxValue, nums[i]*minValue) minValue = min(nums[i], nums[i]*tempMax, nums[i]*minValue) globalMax = max(globalMax, maxValue) return globalMax # arr = [1,-3,2,1,-1] # arr = [2,3,-2,4] # arr = [-2,0,-1] # arr = [-2,3,-4] # arr = [3,2,1,2,3,-3,-9,8] arr = [3,-2,-1,2] print (maxSum(arr))

[@satya1067]

Awesome explanation 🔥🔥

[@sciencecosmos5126]

class Solution { public int maxProduct(int[] nums) { int n = nums.length; int result = Arrays.stream(nums).max().getAsInt(); int min = 1; int max = 1; for(int i=0;i

[@thevagabond85yt]

A[]= {-2,-9,0,0,3,4,0,0,11,-6} ans=18 ; But, After 3rd iteration, currMin=currMax=1; (or if u skip if loop then currMin=currMax=0) Desired result which is prod of first 2 elt, doesn't get destroyed as it is stored in maxProd variables💐

[@sampannapokhrel]

What if the array is [-4,-2,-3]. It doesn't work as it would be -8,8 and then -24, 24. But it will never be +24 multiplying these three. Am I missing sth? Edit: I understood it by researching a little more that -2 as the minimum that you got there is not by adding negative in-front of the maximum one, it's if you have to find the minimum and that would be by just taking -2. So for -4,-2,-3 would be -4, 8 --> -24, 12.

[@mandy1339]

I could think of a non dynamic programming solution in about 1 hr. (Do running cumulative multiplication from left and one from right and take the max) However I struggled to see the dynamic programming approach.

[@shrn]

Great idea with the running cumilative multiplication from left and right

[@sahilverma6160]

My solution simple and easy from functools import reduce from operator import mul a=[2,3,-2,4] b=[] for v in range(len(a)): for i in range(len(a[v:])): b.append(a[v:][:i+1]) print(max(b,key=lambda x: reduce(mul,x)))

[@im_another_you]

Hi NeetCode - Kudos to you Sir. Beautiful explanation.

[@Trueblue4ever559]

The if-statement actually does break the solution, since it fails to detect when 0 itself is the max in the array

[@anilpank]

It is a very crisp solution. The challenge however is how to train your mind that solutions like these strike automatically.

[@vaibhavpatil1152]

thanks man.. keep posting videos .its very helpful.

[@DNHRobot]

the zero thing didn't make sense to me. It makes more sense if you do the product or just take in the number by itself. Like in the first min, you took only -2 and didn't do any product. So the max of 0 would just be the number and min would be 0

[@ianokay]

"Do you at least agree with me, that if we want to find the max product subarray of the entire thing, it might be helpful for us to solve the sub-problem, which is the max product sub-array of just the full two elements first, and USE THAT to get the entire one. Okay, that makes sense". You added the last part so matter-of-factly but I didn't get at all why that makes sense. Why is multiplying the current number by the preceding two numbers somehow some magical trick to this?

[@ikthedarchowdhury8947]

Do we have to store the curMin? I tried without it and it is working fine with all edge cases.

[@samrj444]

Shouldn't brute force be O(n^3)? We have n^2 sub arrays and calculating product for each is an O(n) operation.

[@shaksham.22]

This is one of those question where in order to come to the optimal solution during interview you should have had solved this before atleast once.

[@namanvohra8262]

Very good explanation! But why do u initialize res to the max of nums?

[@jasonuranta7653]

Hi! Can someone explain why you don't need an if statement for the 0 case in order to set the curMax and curMin to 1s? To my understanding if the next n is 0 then curMax = max(n * curMax, n * curMin, n) would just end up as curMax = max(0 * curMax, 0 * curMin, 0) which would be curMax = max(0, 0, 0), getting you curMax = 0. Vice Versa for curMin too. So it seems like that if statement for the 0 case is necessary to me. Thank you!

[@dineshpabbi7005]

I wonder how can one figure out such logics. I feel very demotivated when I cannot figure out a solution. I created a DP solution which passed all cases except last 2 because of memory error...