Maximum Product Subarray🔥 | Array | Love Babbar DSA sheet | Hindi
Vložit
- čas přidán 26. 07. 2024
- Time Stamps :
Problem discussion : 0:00
Approaching the problem : 02:45
Dry Run Algorithm : 05:55
Algorithm discussion : 12:35
Code explanation : 13:00
Time Complexity Discussion :13:40
Time Complexity : O(n)
Space Complexity : O(1)
Maximum Sum Subarray : • Max Contiguous Subarra...
Problem Link : practice.geeksforgeeks.org/pr...
C++ Code Link : github.com/Ayu-99/Love-Babbar...
Python Code Link: github.com/Ayu-99/Love-Babbar...
Love Babbar DSA Sheet : drive.google.com/file/d/1FMdN...
Please like, share and subscribe if you found the video useful. Feel free to ask in comments section if you have any doubts. :)
#DataStructuresAndAlgorithms
#LoveBabbarDSASheet
#interviewpreparation
Maximum Product Subarray solution
Maximum Product Subarray Leetcode
Maximum Product Subarray C++
Maximum Product Subarray C++ Hindi
Maximum Product Subarray Hindi
Checkout the series: 🔥🔥🔥
👉 Array: • Arrays
👉 Recursion : • Recursion
👉 Stack and Queue : • Stack And Queue
👉 Greedy : • Greedy
👉 Dynamic Programming : • Dynamic Programming
👉 Leetcode contests : • Leetcode contests
👉 Leetcode June Challenge : • Leetcode June Challenge
👉 Leetcode July Challenge : • Leetcode July Challenge
LIKE | SHARE | SUBSCRIBE 🔥🔥😊
I found this solution from the leetcode discuss section. I hope it will help to understand the approach in depth:-
Credits :- ArshadAQ
Let me reason the solution.
There are 2 possibilities - either the number of -ve numbers is even or odd.
1. If they are even, then obviously we would want to include all of them(in fact the whole array(unless for zeros)) to maximise the product. This is because multiplying an even number of -ve numbers would make the result +ve.
2. If they are odd, then we would want to exclude at most(to maximise the product) one -ve number from our product. So, now the question is, which -ve number to exclude? There are 2 possibilities - first -ve num or last -ve num.
a. Note that, you cannot exclude a -ve number that is not the first or the last, because, if you do so, you will need to exclude all(because you are breaking the product at this point) other -ve nums following that -ve number and then that needn't result in the maximum product.
b. Remember, that our goal is to leave out only 1 -ve number so that we can maximise our product.
c. Note: We are leaving out one -ve number, so that we are able to make the number of -ve nums even. Having said all that, now the question is whether to exclude the first -ve num or the last -ve num in the array. We can only know the answer by trying both.
d. By taking the product from the beginning of the array, you forcefully include the first -ve number and exclude the last -ve number
e. vice-versa for taking the product from the end
To further explain 2d,e, let me take an example:
Assume the array has an odd number of -ve nums. The first -ve num is -2 and the last -ve num is -3. So the array is .....-2.......-3.......
The maximum product can either be made of all numbers from the beginning of the array to the first non-zero number just before -3, or from the end of the array to the first non-zero number just after -2.
This is why we are considering two possible products, one from the beginning and one from the end.
But wait, you might be thinking, why we are still continuing to multiply even beyond -3(forward iteration) or beyond -2 (backward iteration). That's all actually waste, as the product is only going to increase in negativity beyond those points. The maximum is already updated, so this doesn't affect at all.
Hope you find this useful!
Thanks for sharing :)
Intuition explained very well ayush thanks for sharing... This is pretty simple and straight forward method without confusion..otherwise I have seen other approach in which you will have to maintain min_product too and I found this method that ayushi explained in her video and you explained here is less confusing and time+space complexity is also same. That's great.☺
this code is not generalized one because it won't work for some test cases like array containing consecutively negative elements etc
@@ABDULRAHIM-cj6hk It will work for all test case if you are handling the 0 . since I am updating max value in every iteration .
Nice explanation.
Abe yaar kab se solution samjhne ke liye khap rha thaa....ab jaake aaya....thank you yaar
Chill hai yr, I don't know why I'm getting punjabi vibes :)
excellent and crystal clear explanation sister.these type of teachers we want..
Thank you for this beautiful solution. It was amazing.
Your journey was soo inspiring. Thanks a lot for sharing your journey and knowledge with us
My pleasure :)
You are so good in explaining logic! These type of content creators we want!
Thank you so much Harshwardhan 😊😊 means a lot to me 🤗🤗
I was struggling with some problems and you explained them as they are nothing. Thank you so much sub +1
Thank you so much Tushar :)
Thank You for solution, approach and explaning the dry run of the code
I'm overwhelmed by listening your journey. Keep rising ✨
Thank you 😊
Hi , just loved your approach . Its super easy to remember . Thanks ✌
Welcome Sourabh, glad it was helpful :)
best approach i have seen so far,nice concept as i saw many other doing the same swapping (out of my mind lol)approach without getting the point why that different from max subarray sum /kadane's algo
Glad to see you put effort to crack this prob in debt :D
I did it more better way see this
long long maxProd=arr[0];
long long prod=1;
int i=0,j=0;
bool flag=true;
while(i
Your explanations are always very easy to understand. Thank You👍
So nice of you, thanks Prashu 🤗🤗
That's a brilliant approach. Thanks for sharing.
Welcome Yash, glad it was helpful :)
Thanks for all your efforts. Smart Approach.
Welcome. Glad it was helpful :)
Thank you so much :)
Was looking for this type of explanation😍
Thanks Abhishek😊
Ayushi finally watched your videos to get the intution behind it. Well explained. You are really helping ppl like me who wants to learn coding and you are giving the hope that DSA ho jayega badi bat nhi. :) Awesome explanation.
Thank you so much Jitendra, means a lot 🤗
thank you!! specially how to approach the problem was well explained
Welcome, glad it was helpful 🤗
Thank you so much for this easy solution. I was searching the solution of this question since so far
Welcome Abhishek, glad it was helpful :)
Great content!! Great explanation!!
Thanks, glad it was helpful 🙂
Wow ! Amazing explination
thank you Shilpa :)
Jabar dast samjhata aapne to
Thanks.... You explained it clearly
Welcome Tanya, glad it was helpful 🤗
Wonderful Approach!!!!
Thank you, glad it was helpful 😊😊
loved it💖
Glad it was helpful :)
Wow this approach is hell lot better than the swap approach! Thanks!!
Welcome Shreyansh 🤗
Excellent, no one explained it like that.
Thanks Avi :)
thanks mam for this awesome explaining way of yours
Welcome Mohit, glad it was helpful 😊
Great explanation ayushi . your channel deserves more reach :)
Thank you so much Vishal🥺😊🙌🏻
this video really helped thank you soo much maam
Welcome :) glad it was helpful
Thanks very elegant solution :)
Welcome Anurag, glad it was helpful :)
doing good work...keep up!!
Thanks Abhijeet :)
Great explanation 🔥🔥
Thank you. Glad you found it useful :)
Thanks for easy explanation
You are welcome Suleman 🤗
love u didi......
well exp
Great explanation.
Thank you Tanya :) glad it was helpful
Great explanation
Thank you. Glad it helped :). Please share channel with your friends and juniors🙏🏻
Amazing 👍👍
Thank you Neeraj :)
keep it up sister, best of luck pls make all 450 questions, i will se all ur vedios
Awesome explanation
Thank you :) glad it was helpful
your videos are really helpful to us
Thank you so much. Means a lot😊
@@AyushiSharmaDSA can you please tell us that whether this love babbar 450 series is enough for dsa practise for big MNC's or not?
@@viralchingaari2184 it will cover most of the concepts. But it depends, even after doing it , if you still feel that you need to do practice, then it's not enough :)
Thanks very much 🙏
You are very welcome🤗
Very good explaination
Thank you, glad it was helpful :)
thank you for this beautiful solution ❤
welcome, glad it was helpful :)
@@AyushiSharmaDSA glad to see you back :)
@@JohnWickea yup, thanks John :)
Nice explanation 👍👍
Thank you 😊
is there any better approach than this? only from L->R ?
Thanku didi video ekdam ache se samaj aa gaya :), ek question aur tha agar hamlog ko woh subarray return karna raha toh, kaise karenge
[-4,10,10,-2,5] i think this test case is enough to break this code, well every approach is different and good ,but the level at which you are thinking is crucial ,btw nice soln.
this case will also pass think properly
💯💯💯
Thank u ayushi di..... 😍😍 m adha soln soch chuki thi kyuki maine sum vala q kr liya tha.... Thanks apne is q ko kadane s thoda connect kiya bs yahi nahi soch payi ki agr ek elemnt left m neg h to sbko neg kr dega how to handle it.... Thanks ❤❤again 3,4 video d3khi but nobody relate to kadane algo
Welcome Ritika, glad it was helpful ❤
best solution
thank you, glad it was helpful :)
Mam you are helping alot thanks for amazing content , will you solve the all Que. of love babbar sheet ?
Yes, I will solve all the questions in sheet
@@AyushiSharmaDSA Mam I subscribed to your channel but this answer(Slove all Love babbar DSA sheet) made me turn on notification. Thanks for helping us🙏
@@heavenlyway5824 thanks🥺 means a lot 😊
Even today the first one😁
✨♥️
Thanks
Welcome 🤗
Nice apki voice achi lgi
OP explanation @Ayushi Sharma
Thank you Manas :)
Hi @ayushi, instead of returning the maximum product we are asked to return the sub-array which produces the maximum product, how can we achieve that?
in that case, we will have to maintain start and length variables
@@AyushiSharmaDSA can you please help me out with the code or the resource please?
please explain how it is guaranteed that when traversing from right to left also we will always get the correct answer. This code is excepted but I didn't get the intuition behind it.
You have to traverse from both left to right and right to left.
Didi Previous year ke questions enough hai for placements and company wise. Because previous year ke questions ki practice gfg se kar raha hou thou previous year ke questions kafi hai interview ko crack karne ke liye
Learn concept and build approach, exact question does not come in the interview
Python solution:
res = max(nums)
minp,maxp = 1,1
for num in nums:
minp,maxp = min(num,num*minp,num*maxp),max(num,num*minp,num*maxp)
res = max(res,maxp,minp)
return res
best :,*
Thanks, glad it was helpful :)
Op
🥺🥺🙌🏻 thank you Uday
What for this test case
-1 2 3 4 -5
Instead of using two loops. We can use only single loop same as kadane algorithm.
#include
#include
using namespace std;
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0; i>arr[i];
}
int product = 1;
int mx = INT_MIN;
for(int i=0; i
This approach will not work for negative numbers
@@sumitk8842 if we replace if condition by product
but this code will also not work for all the test cases as it gonna fail in this one- [-3,-1,-1], so the best approach is in the video itself , i.e. if() condition not including the less than term
Mam I want to be successful like you☺️
Keep practicing. :)
Aise hi cmnt krte reh ho jaayega
How to solve this problem in JavaScript?
Any other way of getting a good job without too advance dsa
One test case will fail: if the array is [-2,0,-1] your code will give 1 as the output but actual output is 0.
+1
this test case failed coz we initialized the product as 1 whenever 0 came and we didn't check if 0 can also be a max product ,so there is a small update for this case we have to also check for the max product before initializing product as 1 and after initializing product as 1 we have to use continue keyword to skip the lower part.
you just need to make max(max, 0) whenever we are initializing the product to 1
this code can't handle multiple 0's
like [ 0 0 -5 0 0 ] it will result in 1
but answer is 0
it will handle check again
Hello Ayushi thank you for making these amazing videos. I have one doubt can you please help me in that. I was thinking whether it is a good approach to see the solution. I mean is it good to see the solution or give more time to the question. Like I have to see solution in most of the questions. And I also forget the logic of previous question while solving present one. I mean I solved Best time to Buy and Sell stock question . After 4 days when I tried to solve that question again it was taking time to think the logic. So can you please tell how to remember the logic. I dry run the code and write by myself whether I see the solution also. As now I am in 3rd year and I have to remember these logic.
Hi Ashu. I am glad these are helping.
See, if you are solving a question try to think the approach for about 15-20 mins, then you can see the solution. And, if you forget the approach, then its completely fine. Happens with everyone. Just again do that question. Write the name of that question somewhere and revise it after some days again
@@AyushiSharmaDSA Thank you for the reply. I will do what you suggested.
Thank you once for these amazing videos and explanation.
I am glad they are helping
@@AyushiSharmaDSA Hey I solved mostly all of the questions from array of babbar DSA sheet. But now I was trying to solve the question in leetcode I can't remember the logic. How will I remember till my placement.
Sorry for asking same question but I want ask whether I am learning in right way or not because if I can't remember the logic then what is the use of doing these question.
@@ashu3970 don't worry, solve the question again, write the name of problem and revise it again after few days. And yes, understand the logic and how to get to that approach :)
Hi ma'am ,
Great explanation but I am getting time limit extended error .Is their any other way ..?.BTW thanks for explaining the DSA sheet question 😅
Hi Niraj, glad you found it useful. Can you share your code once
@@AyushiSharmaDSA
import sys
a = [-8,5,3,1,6]
def maxprodarray(a):
n = len(a)
max_product = -sys.maxsize - 1
current_product = a[0]
for i in range(1,n):
current_product = a[i]* current_product
if current_product > max_product:
max_product = current_product
elif current_product == 0:
current_product = 1
j=n-1
current_product = 1
while j>=0:
current_product = current_product * a[j]
if current_product > max_product:
max_product = current_product
elif current_product == 0:
current_product = 1
j-=1
return max_product
r = maxprodarray(a)
print(r)
may i know what do we generally call this approach like name?
Hi, I'm also not sure name of this approach :)
You didn't explain what happened to our overall answer after the first loop when we completed the second loop as well, how does the maxp get affected by both the loops separately and after both of them complete. Came here to understand that part but left disappointed.
Check video properly she has explained, in 2nd example max product is -8 acc. to first loop and after iterating through second loop correct answer will become 90.
the statement "prod=1" in between the for loops, what is that for? can someone explain this.
in this we are iterating from right to left i.e from n-1 to 0 so we initialise it as prod =1 as same we done when we started iterating from left to right
@@Deepakkumar-tq7pe oh okay. Thanks
2 array me problem ati hai woh tricky hai.
Maximum subarray sum wala simple hai.
also can you please tell what source have you used to discover this solutions
Hi Devendra, I got to know about this approach from youtube only(not remember exactly from which channel) :)
Instead of 2 for loops we can check both sides using a single for loop
Take product 1 and max1 for left to right
Take product 2 and max2 for right to left
Return max of max1 and max2
why do we iterate over array in 2 direction??left to right se kyu ni sirf?
@@ritikji2037 explain kia h video me agar first element -ve aa jayega to first loop fail hoo jayega isliye piche se bhi loop lagaya h
Will this approach cover the test case -8 5 3 -1 6? According to this approach answer will be 6 but correct answer should be 15
No sister answer number of -ve's are even (-8 and -1) so annswer will be multiplication of all array
Didi please sheet complete Kara dena . I know you are now placed in Walmart but still try Karna Ki ho jaye
Yes, I will try my best :)
MATH BEHIND THE PROBLEM:
/*
If you are provided an array of positive and negative elements then following observation suggests that maximum product subarray will never lie in middle i.e either the maximum product subarray will always :
1: start at 0 index and end at any index (in right)
OR
2: It will start at any index(at left) but always end at last index
OR
3: it will start at 0th index and end at last index.
Case 1:
(Left side product is +ve)+ve Subarray Product(Right side product is +ve)
=>Not possible that a subarray can exist in middle, maximum product will come by multiplying the entire array (i.e maximum product subarray will start at 0 index and end at last index)
Case 2:
(Left side product is -ve)+ve Subarray Product(Right side product is -ve)
=> Not possible that a subarray can exist in middle , maximum product will come by multiplying the entire array (i.e maximum product subarray will start at 0 index and end at last index)
Case 3:
(Left side product is +ve)+ve Subarray Product(Right side product is -ve)
=> Not possible that a subarray can exist in middle, maximum product subarray will always start from index 0,
i.e maxSubArrayProduct= Left side product * Subarray Product
Case 4:
(Left side product is -ve)+ve Subarray Product(Right side product is +ve)
=>Not possible that a subarray can exist in middle, maximum product subarray will always end at last index,
i.e i.e maxSubArrayProduct= Subarray Product * Right side product
Case 5:
(Left side product is +ve)- ve Subarray Product (Right side product is +ve)
=>Not possible that a subarray can exist in middle, maximum product subarray will start at 0th index or will end at last index,
i.e maxSubArrayProduct=Math.max(Left side product , Right side product)
Case 6:
(Left side product is -ve)- ve Subarray Product (Right side product is -ve)
=>Not possible that a subarray can exist in middle, maximum product subarray will either start from zero index or it will end at last index
i.e maxSubArrayProduct=Math.max((Left side product * Subarray Product), (Subarray Product * Right side product))
Case 7:
(Left side product is +ve)-ve Subarray Product (Right side product is -ve)
=> Not possible that a subarray can exist in middle, maximum product subarray will always end at last index,
i.e maxSubArrayProduct= Subarray Product * Right side product)
Case 8:
(Left side product is -ve)-ve Subarray Product(Right side product is +ve)
=>Not possible that a subarray can exist in middle, maximum product subarray will start at 0th index
i.e maxSubArrayProduct= Left side product * Subarray Product
The above algorithm can also be made to handle 0 as well,by resetting the current subarray product to 1 if the current subarray product becomes 0. (i.e when current value is 0).
*/
class Solution {
public int maxProduct(int[] arr) {
long currentProduct = 1;
int maximumProduct = Integer.MIN_VALUE;
for (int val : arr) {
currentProduct *= val;
if (currentProduct >= Integer.MIN_VALUE && currentProduct = 0; i--) {
currentProduct *= arr[i];
if (currentProduct >= Integer.MIN_VALUE && currentProduct
Sorry, but now yours solution is no more accepted on GFG, it only passes 53 test cases, the first test case where it fails is:
13
3 12 15 23 33 -35 30 -40 -30 -30 -30 26 28
gfg article is shit bro, there they asked to find maximum possible sub array product even she also explained the same, but they given different question which asks to find maximum product of whole array possible. -2 -1 0 4 0 -2 for this test case their output is 16 but it should be 4.
I am getting error in this code when i try to do this via java .
can you please figure out the error . I have already tried so much .
class Solution {
// Function to find maximum product subarray
long maxProduct(int[] arr, int n) {
// code here
int maxP=Integer.MIN_VALUE;
int curP=1;
for(int i=0;i=0;i--)
{
curP*=arr[i];
maxP=Math.max(maxP,curP);
if(curP==0){
curP=1;
}
}
return maxP;
}
}
what error are you getting, in my compiler, its working fine
It is showing wrong output
@@muskanaggarwal9659 can you send the test case
@@AyushiSharmaDSA Input:
13
3 12 15 23 33 -35 30 -40 -30 -30 -30 26 28
Its Correct output is:
15492708000000
And Your Code's output is:
2112363520
this is the first case where my code failed .
Can you please look into this once anyone
those who are strugling with gfg article, there they asked to find maximum possible sub array product even she also explained the same, but they given different question which asks to find maximum product of whole array possible. -2 -1 0 4 0 -2 for this test case their output is 16 but it should be 4.
sound quality thora better ona chahiye tha
Working on that😅
@@AyushiSharmaDSA aap Walmart me hona
@@pranaykumar9433 yes
0,0,-5,0,0 this test case will fail for your code it's correct output is 0 and yours output will be 1.
Intialize the max to nums[0]
@@vidyaarkeri7930 I will check✔️
Very well explained
Thanks ☺️
0 0 -5 0 0 for this its showing 1
bandi mei dum hai!!!!
🤗🤗🥹
your code is not working for [-1,-2,-3,0]