Maximum Product Subarray | O(N) | Geeks for geeks | GFG | Hindi | Problem Solving | FAANG | Shashwat
Vložit
- čas přidán 27. 06. 2021
- Java Plus DSA Complete Placement Course:
• Java and DSA Course Pl...
Coding Interview Problem Playlist:
• Problem Solving | Prod...
Problem Statement:
Given an array Arr that contains N integers (may be positive, negative or zero). Find the product of the maximum product subarray.
Problem Link:
practice.geeksforgeeks.org/pr...
Company Tags:
Facebook | Amazon | Microsoft | Netflix | Google | LinkedIn | Pega Systems | VMware | Adobe
Instagram Handle: (@shashwat_tiwari_st)
shashwattiwari.page.link/shas...
#ShashwatTiwari #coding #problemsolving #leetcode #hackerrank #hackerearth #codechef #codesignal #algorithms #javaprogramming #sde #placement #programming
This is a very old video, for better sound and camera quality DSA videos, learn from the below playlist!
Java Plus DSA ( Java + DSA + Problem Solving )
czcams.com/play/PLQ7ZAf76c0ZPVdhV1bAjFv0bQc1xHURzE.html
HIDDEN GEM on CZcams! All your solution and explanations are worth the watch!
it fails for -2 0 -1
You are right, but still answer is accepted by gfg.
*Please Read this*
In the video, I was showing the output of "max" and "res" in the same variable (I realize it now). But the explanation is no different. We have to look for a maximum of "temp1", "temp2" and "current", as well as their minimum. Please don't confuse yourself. This is the flow:
max is -3
min is -18
res is 6
max is 180
min is -10
res is 180
max is 0
min is 0
res is 180
max is 2
min is 0
res is 180
180
Keep going
Very well explained brother, Keep it up :-)
Thank you so much 4 all your videos
Nice explanation sir
Awesome video!!
Thank you so much!!!
that continue statement is not needed. coz let's take this example : {-2, 0, -1}. you'll get -1 as ans whereas 0 is expected.
Yes correct. Thanks. Updated the solution 👌
Loved it
Sir how are you forming this concept like at 8:55 their is no need of -60 but then also you are multiplying it!!
Negative numbers might become positive that's why we are taking Negative numbers. Also I have made this quite back, but somewhere I have done one multiplication error, may be you spotted that so you are correct.
All you need to know is.
Current element, min product so far and max product so far, your ans will be one of these.
Also, I have already made a video on kadanes algorithm , this question I have solved there it hardly takes 5 lines and that code is way more simpler than this.. Link is in the comments.
Thank you yaarrrr!!!!
Your code and explanation is different.
After first iteration, in the video explanation, max value is 6 and min value is -18.,
But as per code, max value is -3.
Larger of temp1 and temp2 is compared with current a[i]. Max already set value is not taken into account.
But in video explanation, it is considered.
In the video, I was showing the output of "max" and "res" in the same variable (I realize it now). But the explanation is no different. We have to look for a maximum of "temp1", "temp2" and "current", as well as their minimum. Please don't confuse yourself. This is the flow:
max is -3
min is -18
res is 6
max is 180
min is -10
res is 180
max is 0
min is 0
res is 180
max is 2
min is 0
res is 180
180
Good explanation. But you keep jumping from the right side of the board to the left side and then back to right and then back to left ......
😂😂
you explained well, but there is an issue in your code that at GFG it works. but on the leetcode doesn't pass this test case
[-2,0,-1]. I test it but it did not work for this test case. can you plz tell me what the problem is in your code? or why it did not work plz check.
Check this one.
czcams.com/video/PZN2YkPtUaM/video.html
Just remove the base condition (arr[i] == 0) 👍🏽
Sir I think you miss that case when arr[i]=0 then you are not updating min with 0. You are using continue in if block then min never will be updated with 0.
No, I explained it 0 is acting here as a delimiter, in the code also I have updated min and max with 1 whenever we hit 0.
This is because we are finding a product here, so if I update min and max with 0, it will be wrong as 0 multiplied with any number will be 0. Therefore, we will update min and max with 1 whenever we see a 0 in the array.
Ok sir
how -60 is comming min ..it not continuous . i m confused, if in place of 0 there is -5 then it will trnalste to 300 making 300 max ...
In the video, I was showing the output of "max" and "res" in the same variable (I realize it now). But the explanation is no different. We have to look for a maximum of "temp1", "temp2" and "current", as well as their minimum. Please don't confuse yourself. This is the flow:
max is -3
min is -18
res is 6
max is 180
min is -10
res is 180
max is 0
min is 0
res is 180
max is 2
min is 0
res is 180
180
i have a doubt regarding your example that why you take min = -60 that means you multiply arr[0]*arr[2] directly does it form subarray brother. And u already told you that we can use min as well.
In the video, I was showing the output of "max" and "res" in the same variable (I realize it now). But the explanation is no different. We have to look for a maximum of "temp1", "temp2" and "current", as well as their minimum. Please don't confuse yourself. This is the flow:
max is -3
min is -18
res is 6
max is 180
min is -10
res is 180
max is 0
min is 0
res is 180
max is 2
min is 0
res is 180
180
See,
I am not multiplying arr[0] and arr[2].
it is going in continuation. You can watch the kadanes algorithm video on my channel. There I have explained this question also. You will get all your answers there.
2:47 Yhi tak thaa jo bhi thaa
bro, the logic doesn't work for this test case : [-2,0,-1]
I have updated the solution. Remove the continue statement and it will work fine. Solution is in the video description
@@shashwat_tiwari_st it works. Thanks!
If your solution is not passing all test cases, see below video.
This question can also be solved optimally using Kadane's algorithm!
Watch it till the end:
czcams.com/video/PZN2YkPtUaM/video.html
Sir,I feel this similar to kadane algo ony this is of max product and that is of max sum...or is there another solution of this problem using kadane algo
done
GFG IDE is not accepting it
hey, I just rechecked and it's working, the solution link is also given in the description, you might have done some typing mistakes, check the solution in the description of this video, let me know if you still face any issues.
I think you dont need to use the continue statement
for e.g. in test case [-2,0,-1]
answer should be 0 but min and max gets updated to 1,1 and we move to next index
@@abhishekpaswan7821 yup yup, you are right, updated the code. Thanks😃!
ummed jaga sakta h apne andar ..lol ...😂😂😂
It's kadanes algo
Not exactly, but yes this problem can be solved using kadanes algorithm, you can check kadanes algorithms video. There I have discussed this problem as well. Code differs a bit.