Maximum Product Subarray | Array | Love Babbar DSA Sheet | Amazon🔥
Vložit
- čas přidán 19. 10. 2021
- #arrays #coding #programming #competitiveprogramming #coding #dsa
Hey, Guys in this video I have explained how we can solve the problem 'Maximum Product Subarray '.
Join our Telegram Channel for more Information
🔰 Telegram Channel Link = t.me/CodeLibrary1
🔰 Telegram Discussion Group Link = t.me/CodeLibraryDiscussion
Subscribe Our 2nd Channel = / @codeupwithtwins6728
🔰 Array Playlist = • Love Babbar DSA 450 Qu...
🔰 String Playlist = • Love Babbar DSA 450 Qu...
🔰 Searching and Sorting Playlist = • Love Babbar DSA 450 Qu...
🔰 Binary Tree Playlist = • Love Babbar DSA 450 Qu...
🔰 Linked List Playlist = • Love Babbar DSA 450 Qu...
🔰 Graph Playlist = • Love Babbar DSA 450 Qu...
🔰 Dynamic Programming Playlist = • Love Babbar DSA 450 Qu...
🔰 Informative Videos = • Informative Videos
🔰 Love Babbar DSA Sheet: drive.google.com/file/d/1FMdN...
Follow us on Instagram:
🔰 Shailesh Yogendra: / shaileshyogendra
🔰 Yogesh Yogendra: / i_am_yogesh_here
Follow us on LinkedIn:
🔰 Yogesh Yogendra: / yogesh-yogendra-26bbb518a
🔰 Shailesh Yogendra: / shailesh-yogendra-8b13...
Hope you like it. Comment if you have any doubt
LIKE | SHARE | SUBSCRIBE
Very well explained Yogesh, please keep uploading content. Don't let the channel die.
Read many solutions on leetcode and watched several YT videos, but finaly got clarity from this video. Thanks man.
This was just so amazing, beautifully explained
bhai mza aa gya iska solution kisi ne b itni ache se explain ni kia h thnk u
Thanks dude I was struggling to understand the gfg solution but you made it so easy!
Thanks....crystal clear....short, crisp & intuitive video...
Maza aagaya what an awesome explanation. Crisp and to the point. Ty!!!
Fantastic approach!!
Really, Very Good Explanation...Thank you so much...
You deserve more subscriber man great work!
nice explainations, thanks for helping!
excellent expalation, thanks :)
Ulta sidha batna with confidence 🔥🔥
Very good concept. GeekforGeek ka solution nhi smjh aa rha tha ...👍👍
Bhaiya, please complete the whole dsa sheet.
Your explanation is great.
Great Explanation Sir ❤✨🙏🙇♂
bro not passing all the test cases in java
great explanation 👍👍👍👍,just one question what thinking brought to you in mind that keeping this maximum and minimum is covering all the subarrays like for the first time ??
Basically I want to know about the intuition to this approach
!
superb explanation buddy.
Great Explanation ............
great explanation✨👍🏻
Doesn't understand that what happens when 0 comes into the array??
Now got it 🙂✌🏻
Amazing explanation!!
Great Explanation. Lots of Love from pakistan
why cant we apply kadanes algo in it??
😍😍
I was waiting for the explanation of your swap thing to subscribe you.
Basically,kadane's jaisa hi approach hai
Ditto h almost
nice explanation
which slate you are using for writing?
Very Well Explanation of code. Really appreciate what you do. But not satisfied with the logic building part.
logic building will come from recursion. If you haven't done the recursion part of this problem then it's high chances that you are going to cram the solution no matter which tutorial you see. So try to first get a recursive soln and then move on to array.
Nice Explanation
Nice explanation bhaiya
Badiya.
ty bro
Great
❤❤
Bdia bhai tum kaise soch lete ho hmse to socha hi nahi jata sirf brute force ati h
great video!. one request, please talk with slow speed
Bro what about matrix problm in love babbr not able to find
great
I wrote the exact code in js , but it's not working , giving wrong ans
Noiceee
how to find length of that sub array
Bhai aap ne iske liye intuition kaise develop kiya ?
hello Sir I have a question,
what if we want to print the subArray also that is givng us maximum product?
if anybody knows the answer please reply
yeah you have to print till the position of the array where you have find the maxsum.
Do we have to write main function in coding test??!
Tht depends on platform. If its already written you ve to write only function. It will be mentioned or u urself can see in code section
Great thought process, but just want to know how can you think of such solution during interview and you have not heard of such question before?
I also thought so! How can someone think of such approach in small amount of time!
@@tanujghatge9287 you have to prepare every algorithm possible , be prepared for everything that is already there in books and internet . Practice each and every approach available., because there is no approach that you can discover on the day of interview, approaches and algorithms have already been discovered, you just need to know them.
@@devchaturvedi3651 Thanks for the advice brother.
i guess by practicing more questions only we can think of such approaches
Soln doesnt work for -2,3,-4
Ye solution ek bande ne daala tha leetcode par jo University teacher ka hai
if 0 come then????????????
On gfg , this exact code fails but instead the below mentioned code works and idk what is wrong
long long ans=arr[0],maximum=arr[0], minimum=arr[0];
for(int i=1;i
How to deal if arr[i]=0??
@@aasthagoyal5059 just like othet cases only. The max and min will suffice for them
Great explanation brother.
bhai koi aur test case bhi smjhate toh saare doubt clear ho jaata
Optimized soln from -> 3:10
well explained!!!!
Clear explanation. Thanks !!
if someone wants AC C++ code:
class Solution {
public:
int maxProduct(vector& nums) {
// ma mi technique:
int n = nums.size();
int ma = nums[0], mi = nums[0], ans = nums[0];
for(int i=1;i
this will not work if there is 0's in between
It works
if the array has 0 , then both max and min becomes 0 and we lose the previous max right? so what do we do? your code doesnt work for this type of test case:
1
5
6,-3,-10,0,2
your output =360 , expected output = 180
Exactly
no output will be 180 only. coz at each step, we are calculating the max of ans and ma and storing them in ans. so at the 3rd index(1-based index), we got 180 which gets stored in ans, after that, we don't require the previous ma because now we have encountered 0. so we have to continue from these steps only.
May be this code will help you to understand:
ll maxi = a[0],mini=a[0];
ll ans=a[0];
for(ll i=1;i
The answer coming is 180 still as we have already stored our ans we dont require previous stuffs.
@@AMITKUMAR-dj2fv ans will be 180 but what if the elements are like this:1,2,0,-4,-5
expected output=20 but using this code we will get 2 which is wrong
@@sriramdinesh8852 Code Is giving 20 as expected becoz -4 will be stored in mini variable first then when it goes on -5 it will do swapping and then product of (-4*-5) will happen.
Why are you starting the loop from index 1 and not 0?
Coz we have already took mi ma for 0index at starting while decalaring
test case fails for -2 3 -4
Thank You please tell intuition as well
What is the intention behind taking mi (why mi, how it helps to find max prod) that was missing in this video? But it was good.
buddy, its simple, while including elementa into the sub array and multiplyong them, if you encounter a nagative value, then u will get maximum negative product which is wrong
example: 2, 3, -4, 1
max = 2, min =2
max = 2*3 =6 , max = max(3, 6) = 6
min = 2*3 =6 min =min(3,6) =3
max = 6*-4 =-24, max = max(-4, -24) = -24
min = 3*-4 = -12, min = min(-4, -12) = -4
which is totally wrong, where max should contain the value of min, where min should contain max value, right
so this will happen only when we encounter a negative value,
so need to maintain, min and max
always and when u encounter a -negative no first swap, min and max, then the flow will be correct
3:00 -> solution starts from here.
great explaination buddy 🫂
Mera bhi starting mein kaafi saarein wrong answer aaye !! 🤦♂️☠
Your code doesnt work for this TC
[-2,3,-4]
U must have done...
Max(max, max*arr(i))
Instead of...
Max(arr(i), max*arr(i))
Same for min
Bro, bhut fast tha and you were just telling the solution instead of explaining.
Can you make a video for count stairs order doesnot matter also
Ugh
Explain it in English or change the title to Hindi
Ulta kar de
Optimize it with dp what it is part of
what if the array got 0 in it?
bhai this approach is not working when arr[-2,3,-4]
ans = 24 but by this approach ans = 3
Try applying the approach again. Did you forget to swap? Answer is coming 24 only with the above approach...Here is the maxProduct values that it takes -> -2->-6(after swap) -> 24
getting wrong answer with this sol [-2,3,-4]
class Solution {
public:
int maxProduct(vector& nums) {
int maxi = nums[0];
int mini = nums[0];
int ans = nums[0];
for(int i = 1;i < nums.size();i++){
if(nums[i] < 0){
swap(maxi,mini);
}
maxi = max(nums[i],maxi*nums[i]);
mini = max(nums[i],mini*nums[i]);
ans = max(ans,maxi);
}
return ans;
}
};
maxi and mini....in both you're taking max()...take min() in mini.
Mereko ye samajh nahi ata ye sb solution bande khud se kaise soch lete h.
shi mein bro....dekh ke bikul nhi laga ki ye approach work kregi...lekin dry run krke sab chal rha hai
Khud samajh lo pehla
This code will not run in GFG because of a TestCase: [3 12 15 23 33 -35 30 -40 -30 -30 -30 26 28]
You need to add another condition there.
```
int maxProduct(vector& arr) {
int n = arr.size();
int ans = arr[0];
int maxi = ans;
int mini = ans;
int choice1, choice2;
for (int i = 1; i < n; i++) {
choice1 = maxi * arr[i]; // Check Here
choice2 = mini * arr[i]; // Check Here
maxi = max(arr[i], max(choice1, choice2)); // Check Here
mini = min(arr[i], min(choice1, choice2)); // Check Here
ans = max(ans, maxi);
}
return ans;
}
```
Appreciate ur effort, but try to check your codes in multiple platforms before making video.
Dont teach incomplete answers.
What's the reason for taking choice1 and choice2?
Still then the above code doesn't work for the above testcase
@@DebasmitBiswal actually ye gfg platform ki galti h choice lene ka
reason ye hai ki arr[i] int hai aur maxi or mini long long h toh
max(int , long long ) nhi le raha gfg ka compiler
also the condition for 0 is not desribed
the code is used is :
int ans = nums[0];
int mi = nums[0];
int ma = nums[0];
for(int i=1; i 0){
ma = max(nums[i], nums[i]*ma);
mi = min(nums[i], mi*nums[i]);
}
else if(nums[i] == 0){
ma = 0;
mi = 0;
}
else{
swap(ma, mi);
mi = min(nums[i], mi*nums[i]);
ma = ma*nums[i];
}
ans = max(ma, ans);
}
nice explanation