He should have told us how that algorithm was built on what mathematical basis Kadane got the intuition for this problem and developed an O(n) solution
@@RudraSingh-pb5ls intuitive approach would be for each element compare it with all the elements on its right side.. (2 for loops)...add them if(sum>0)...this would take 0(n^2) Which is very similar to kadane algo(we taking 2 pointers one for adding the elements and other for finding the longest subarray sum)is similar to this n reduce the runtime...
@@anjalisingh-sx5ct I know what is kadanes and how it works but the way you guys are explaining is the worst. You just telling me how to do instead of why ? So the question isn't how , question is why !
The variable names make it more confusing than it needs to be (at least for me it did), renaming to sum & result would make it easier to understand. Sum keeps track of max (sum of prev numbers + curr or curr by itself). And then result just keeps track of the largest sum you’ve encountered.
Dudeee I have scraped the entire internet to understand this algo and till now yours was the best, I have completely understood it now, you have not overcomplicated things or undercomplicated it to make it seem tad easy, you have kept the difficulty just perfect.
Although you have only 12.2 k subs, pls don't stop making videos, have patience and keep making such videos, it will take time but you will surely reach 1M subs soon. Don't stop, if you feel your videos are not making money, make videos as a charity to the students.
Sure man :) Even though I don't earn much through RUclips, but by making videos I get to learn as well. Also, teaching is my hobby. So, I will continue :)
Hi, Can you please explain the thought process behind the solution? I mean how did you come up with 'msf' and 'meh'? A detail explanation behind the intuition will be helpful.
if we add have a running sum rs and we claim its part of the maxsum sub array then if we add b :rs+b = maxsum but we notice that maxsum is less than b then rs is negative if so then b = rs +maxsum where b is the maxsum then ou initial claim that rs is part of the maxsum array is false so we drop it in simple word if rs+b is less than b then rs will always weigh us down so we drop it
At 1.26 you have said that kadane algo only works on positive array. For a positive array, entire array is a longest sum contigous block. Considering subarray can also be the whole array.
I mean to say that kadane's algo works when atleast 1 number is positive (I presented it in an ambiguous way). If you have all negative numbers then kadane's was taking max_ending_here = 0 which would never get updated because all numbers are negative and output would be 0. I hope you get it now.
Great logic, I'm currently using this to learn for my Microsoft Interview. Thanks alot man, practiced and memorized this algorithm. I'll try to do it daily. Cheers from Florida, keep up the videos. You got a sub my man.
For Python coders: def maxsubarray(arr): n = len(arr) curr = arr[0] final = arr[0] for i in range(1,len(arr)): curr = max(arr[i],curr+arr[i]) final = max(curr,final) return final
Your explanation is very good . But, one suggestion I want to give , i.e:- you are directly explaining the method it will be better if you explain from sratch like from where this method came and how to get this approach like that ... Thanks for great explanation
In the brute force approach, you said it will be the order of O(n^2). pseudocode for the brute force approach : sum=0 for (i=0 to n) for (j=i to n) //two loops for finding all substrings. max(sum,sum(i to j)) // sum of that substring. I think this brute force approach will take O(n^3) order. Correct me, if I am wrong :)
Nice, But for kadanes algo there is condition of atleast one positive number must be present in array. So, this problem will solve easily by kadane algorithm.
If you find a max value then just save the ending index. After kadane's is done, just parse the array from the saved index in reverse order. Stop when sum value is same is maxSum. That index is your left index :) Congrats, you have now found the window.
dude i dont have any basic ideas about c or c++ and i know python should i learn dp in pyhton or i should learn dp in c++ and learn along what these syntaxes are?
I would recommend you to learn DP by implementing from scratch. The cache in python don't let you learn DP. But, you can skip that and implement all logic yourself and learn it in Python too :)
bro if possible can u 1st make recursive version + memorization of kadance ,Longest common subsequence,and few more parent question its helps us to develop logic and how to use dp in these question. and btw ur explanation is super awesome and easy to grasp thanks brother :)
There is one queston with respect to the above concept. For example if I have arr = [1, -2, 3], then manually i know that subrray with index 2 i.e [3] will hold the maximum sum. I am speaking with respect to contagious array. Subarray by taking the third element is also contagious according to me. If i run the above mentioned concept code, I get the result as 1, which means first element of the array but result from manual approach is not same. Can you please explain me where I am lacking or do i need better understanding of contagious array.
@@techdose4u Number that can be divided only by themselves and 1, i.e 2, 3, 5, 7, 11 etc. I have to find largest subarray under the condition that absolute value of every number of it is prime number.
Initially "msf" is 0(zero) you said. In the second if condition 0(zero) is not less than -2 know. Then second if statement also fails for the first loop. But you explained msf becomes -2 after 1st loop. How is it possible?
When you slide and update your max_so_far, just maintain two int variables which will store the index where you are updating your value. At the end of parse, your index values stored will give the window starting and ending index. I hope you got it :)
I have seen several explanations. But this one is best.
Thanks :)
I don't think so ! He explained the algorithm in a good manner but that's rote learning.
He should have told us how that algorithm was built on what mathematical basis Kadane got the intuition for this problem and developed an O(n) solution
@@RudraSingh-pb5ls intuitive approach would be for each element compare it with all the elements on its right side.. (2 for loops)...add them if(sum>0)...this would take 0(n^2)
Which is very similar to kadane algo(we taking 2 pointers one for adding the elements and other for finding the longest subarray sum)is similar to this n reduce the runtime...
@@anjalisingh-sx5ct I know what is kadanes and how it works but the way you guys are explaining is the worst. You just telling me how to do instead of why ?
So the question isn't how , question is why !
Best explanation on RUclips, thank you so much!
welcome :)
The variable names make it more confusing than it needs to be (at least for me it did), renaming to sum & result would make it easier to understand.
Sum keeps track of max (sum of prev numbers + curr or curr by itself). And then result just keeps track of the largest sum you’ve encountered.
👍🏼
true!
Dudeee I have scraped the entire internet to understand this algo and till now yours was the best, I have completely understood it now, you have not overcomplicated things or undercomplicated it to make it seem tad easy, you have kept the difficulty just perfect.
Thanks :)
When you are so bored coding that you name your variable 'meh'
😅
Best explanation of Kadane's algorithm, Good job TECH DOSE!!!
Thanks
Super video! I applauded for ₹40.00 👏
Thanks for your support :)
This is my favourite RUclips channel for Coding along with mycodeschool.
Great :)
Thank sir I have learnt whole DSA with strong understanding from your channel
Great ❤️
Although you have only 12.2 k subs, pls don't stop making videos, have patience and keep making such videos, it will take time but you will surely reach 1M subs soon. Don't stop, if you feel your videos are not making money, make videos as a charity to the students.
Sure man :) Even though I don't earn much through RUclips, but by making videos I get to learn as well. Also, teaching is my hobby. So, I will continue :)
@@techdose4u You have helped me a lot. You explain the topic very well. Hats off man for your effort.
@@techdose4u thanks sir please keep going... we need your videos
@@techdose4u And here it goes...... You`ve now 65.6k subscribers :)
Stay connected with us ☺️
Magnificent implementation of Algorithm..!!
Keep it up👍
Thanks :)
Great explanation, I was going round and round many videos since last 2 hours. Finally got it
Nice :)
Beautifully Explained !! The best explanation of Kadane's Algorithm !! Keep it up mate !!
Thanks :)
The best explanation of Kadanes Algo!!
Thanks
Trust me buddy, there can't be a better explanation than this! ❤️
Thanks 😊
Hi,
Can you please explain the thought process behind the solution? I mean how did you come up with 'msf' and 'meh'? A detail explanation behind the intuition will be helpful.
MSF - Max So Far
MEH - Max Ending Here
@@vitaliitomas4057 I know that.
if we add have a running sum rs and we claim its part of the maxsum sub array then if we add b :rs+b = maxsum but we notice that maxsum is less than b then rs is negative if so then b = rs +maxsum where b is the maxsum then ou initial claim that rs is part of the maxsum array is false so we drop it in simple word if rs+b is less than b then rs will always weigh us down so we drop it
Best video on RUclips to explain kadane's algo
Thanks :)
At 1.26 you have said that kadane algo only works on positive array. For a positive array, entire array is a longest sum contigous block. Considering subarray can also be the whole array.
I mean to say that kadane's algo works when atleast 1 number is positive (I presented it in an ambiguous way). If you have all negative numbers then kadane's was taking max_ending_here = 0 which would never get updated because all numbers are negative and output would be 0. I hope you get it now.
Great logic, I'm currently using this to learn for my Microsoft Interview.
Thanks alot man, practiced and memorized this algorithm. I'll try to do it daily.
Cheers from Florida, keep up the videos. You got a sub my man.
Nice :)
Thank you, for this nice and clean explanation
Thanks sir :-)
Simple code snippet for easy understanding : C++
int maxSubArray(vector& nums) {
int max_sum = INT_MIN, curr_sum = 0;
for(auto num: nums){
curr_sum += num;
max_sum = max(curr_sum, max_sum);
if(curr_sum < 0) curr_sum = 0;
}
return max_sum;
}
what is auto num?
@@vishnusivan9382 if you use Java it's for (int num: nums) {}
no one can explain it like u.. god bless u
For Python coders:
def maxsubarray(arr):
n = len(arr)
curr = arr[0]
final = arr[0]
for i in range(1,len(arr)):
curr = max(arr[i],curr+arr[i])
final = max(curr,final)
return final
goodjob
how to print that array
Thank you
tum jo aaye zindagi mei baat bann gayi.awesome explanation
Thanks bro :)
You are GOD in explaining algorithms 🙂
I have seen many videos,but this one solved my doubtssss🙏🙏🙏🙏🙏
👍🏼
the best explanation so far found on any source!
:)
Perfect Solution I found.. Thank you so much 👍
for better understanding read the conditions as : a[i] > meh & meh > msf
Thanks for the video, I was trying to solve this problem for 1 day
The best explanation out there
Thanks
@@techdose4u Kindly guide how to print the elements of the desired max subarray
Best Video for Kadanes algorithm.
Thanks 😊
Good explanation. Got more clear to me.!
mast video banai, bhaiya, sab samajh aa gya.
Easy to understand.
arr=list(map(int,input().split()))
maxi=arr[0]
sumi=0
for i in arr:
sumi+=i
if sumi
Clear and informative as usual. Good job.
Thanks :)
Very simple and it works THANK YOU
Fantastic explanation !!
Simple code snippet for easy understanding :
private int solve(int[] arr){
int prefixSum = 0;
int max = Integer.MIN_VALUE;
for (int elem : arr) {
prefixSum += elem;
prefixSum = Math.max(prefixSum, elem);
max = Math.max(max, prefixSum);
}
return max;
}
👍
I dont earn atm, but when i start earning, I'll make sure to support ur channel
Thanks for your support :)
This algo is awesome, the author is supper hero.
🤗
Best explanation so far.
Thanks :)
we can use sliding window algo here to get the exact subarray as well
Nice explanation with all possibilities
🙂
Your explanation is very good . But, one suggestion I want to give , i.e:- you are directly explaining the method it will be better if you explain from sratch like from where this method came and how to get this approach like that ...
Thanks for great explanation
Nobody will watch that as it will increase the length of video. Most people watch the videos when they are tight on schedule :)
@@techdose4u I only watch your videos just because of the explanation part and thought process.
In the brute force approach, you said it will be the order of O(n^2).
pseudocode for the brute force approach :
sum=0
for (i=0 to n)
for (j=i to n) //two loops for finding all substrings.
max(sum,sum(i to j)) // sum of that substring.
I think this brute force approach will take O(n^3) order.
Correct me, if I am wrong :)
Nope it will be O(n^2)
Yes, it is n3.
Yeah even i got this
Bro best one keep making videos ☺️
Thanks :)
Nice,
But for kadanes algo there is condition of atleast one positive number must be present in array.
So, this problem will solve easily by kadane algorithm.
Best 😇😇😇 explanation
Thanks :)
Like these 27 people are even humans?
This is the easiest approach I have ever seen for this algorithm and tech dose have explained it in the best way
Thanks
@@techdose4u Possibly your code doesn't work correctly for multiple test-cases (TCs).
Man outstanding solution my brain cant even think of it
Now you know it :)
@@techdose4u Clean explanation Obviously Yes
:)
excellent video Straight to the point thank you
Welcome :)
Amazing explanation !!!
Thanks
how to track using left and right pointer to get that array
Best Explanation!!
Thanks
very good explanation
Thanks :)
how can we keep trackof subarray indices side by side??? i mean how would iteration take place?
If you find a max value then just save the ending index. After kadane's is done, just parse the array from the saved index in reverse order. Stop when sum value is same is maxSum. That index is your left index :) Congrats, you have now found the window.
how did you get the intuition for that ?
what if we had to return the maximum sub array? for that we will have to use n^2 approach right?
No. You can maintain a left window pointer which will update whenever the current sum falls below 0
@@techdose4u could you please elaborate it more in detail?
@TECH DOSE can u tell why this problem is there in your DP Playlist? How is it related to DP
It's a DP algo.
@@techdose4u So a DP algo can be made without using extra space right??
if (max_ending_here < 0)
max_ending_here = 0;
why this is also working
thankuu it worked for -ve numbers alsoo
Welcome :)
dude i dont have any basic ideas about c or c++ and i know python should i learn dp in pyhton or i should learn dp in c++ and learn along what these syntaxes are?
I would recommend you to learn DP by implementing from scratch. The cache in python don't let you learn DP. But, you can skip that and implement all logic yourself and learn it in Python too :)
Well described!! THANKYOU
helped a lot to understand... Thanks sir
Great content bro !!
bro if possible can u 1st make recursive version + memorization of kadance ,Longest common subsequence,and few more parent question its helps us to develop logic and how to use dp in these question.
and btw ur explanation is super awesome and easy to grasp thanks brother :)
On my way. Currently doing it.
how to get the exact subarray if required?
how do cal indices with same logic? please explain me a bit of it
???
One of the best explanations!! Great work @Techdose4u
Thanks :)
👌👍 excellent sir
Bro this Playlist is enough for clearing MNC Coding interview pls reply.
Very well explaination bro. I loved it.
It's good but not enough. Try to cover as much as you can from all my playlists.
great explanation sir!!
Thanks :)
how did you decide the first element of subarray
When should we update the pointers?
You need to check when value falls below min.
Sir, this logic is not working for [-2,3]
There is one queston with respect to the above concept. For example if I have arr = [1, -2, 3], then manually i know that
subrray with index 2 i.e [3] will hold the maximum sum. I am speaking with respect to contagious array. Subarray by taking the third element is also contagious according to me. If i run the above mentioned concept code, I get the result as 1, which means first element of the array but result from manual approach is not same.
Can you please explain me where I am lacking or do i need better understanding of contagious array.
can any one provide here this algorithm implementation in python....?
How to use INT_MIN in Python 3
i did not understand what is INT_MIN please reply me
can u explain how to find kth largest contiguous sub array instead of largest contiguous subarry using kadanes alogrithm
Can you further explain the statement and give the problem link.
@@techdose4u www.geeksforgeeks.org/k-th-largest-sum-contiguous-subarray/
this one :)
This Helped. Thank You.
Welcome :)
Nicely u explained
You are a life saver. Any advice how do I implement primes into it? Also subbed
Primes meaning ?
@@techdose4u Number that can be divided only by themselves and 1, i.e 2, 3, 5, 7, 11 etc. I have to find largest subarray under the condition that absolute value of every number of it is prime number.
Very well explained sir
Great tutorial...Thank You
Welcome :)
Which software do you use
What is the default value of int_min?
Initially "msf" is 0(zero) you said. In the second if condition 0(zero) is not less than -2 know. Then second if statement also fails for the first loop. But you explained msf becomes -2 after 1st loop. How is it possible?
Great work sir but what is the intuituion behind this algo?
Hi can I know why you modified existing also what kind of issues are you trying to solve?
can u explain why we check this condition if(meh
Best Video 🤞🏻
Thanks :)
shouldnt msf be array[0]?
Nice explanation
Thanks
Sir which app you use for making these videos??
How to print max sum contiguous sub-array?
When you slide and update your max_so_far, just maintain two int variables which will store the index where you are updating your value. At the end of parse, your index values stored will give the window starting and ending index. I hope you got it :)
@@techdose4u Thnx :)
In python it is two lines
meh = max(a[i], meh + a[i] )
msf = max( meh, msf)
you can do that in c++ too
very good performance
Thanks bhaiya :)
nice explanation
Superb bro
Thanks