Best Explanation of Kadane's Algo I have ever seen. The most important thing that you explained the algo into two parts - 1. Find the greatest sum 2. Find the starting and ending indices of subarray containing the max sum
What's n here? If it is the length of the array, I get 22 for the above array that Vivekanand has used for the tutorial. Did you try using it before posting the 2-line answer?
Solution is trivial. Return an empty array. Sum of all elements is zero (since there are no elements). 0 is strictly greater than any combination of negative numbers. You could create a subroutine to scan the array and return this result if this is the case. Total running time should be O(2n) which is still O(n).
Great explanation, I love it. One small simplification may be that max_so_far can be initialized to zero, rather than a[0]. Another advantage of making that change is that if the array is zero-length (size==0) you won't be accessing invalid memory.
you can handle an empty array with a base case that checks for an empty array and simply returns (i.e. if (arr.length === 0) return). If you initialize max_so_far to 0, a test case of [-2] (or any negative number) will fail. I used [-2] as an example because that's the test case I failed on Leetcode lol
can we print the largest sub-array that was found , using Kadane algo?..we can get the end point of that sub-array but how do we get its starting point.
I've seen this problem posted as a dynamic programming problem on Leetcode. I like this way better though. Is there any argument to do DP over this way?
your understanding of the problem is Bad..... The way I see the problem is 3 cases : Life Hope and Death. We'll take 2 sum variables' : prev_sum and current_sum. Life is when we encounter only positive number: we will update prev_sum in this case Hope is when we encountered a negative number but that negative number has not made my current sum less than zero so there is still hope that some next number may repair the damage done by the negative number. : we will update prev_sum when current_sum > prev_sum Death is when the current sum becomes negative .....so now in this case we have re-initialize the starting point for calculating current sum Below is my smart : : code public static int findLargestSum(int a[]) { int end = 0; int current_sum = 0; int prev_sum = 0; while (end < a.length) { current_sum += a[end]; if (current_sum < 0) { // death case current_sum = 0; } if (current_sum > prev_sum) { prev_sum = current_sum; } end++; } return prev_sum;
One more observation ... What if the array consists entirely of negative values? This algorithm will report start and end both zero, which is a subarray of length 1. It seems like it may be better, in general, for the result to be reported as a start index and a length (rather than end index). Then the correct answer in this case (all elements negative) is start = zero (or really anything), length = zero. I implemented this here: codepad.org/irM2hs1b
Hi Vivekanan sirji, you are doing a great job.. I have watched some of your other videos too and must say they are simply awesome and to the point.. It will be even better if you could organize your uploaded videos into a playlist, it will direct the users to your other videos.... just a suggestion :)
Will this algorithm work for an input array {5, -2, -1, 3, -4}. Just a second set of eyes to verify we get the result as maximum length of the subarray is 4. Please help!
faulty explanation.. will fail for sample case like [-2 5 -1] where the output of the maxsum with his logic is 3 but it should be 5 actually. *max_so_far* at the starting should be the maximum element of the array.
Can you please make a video on Largest subarray with equal number of 0s and 1s with O(N) time complexity and also please make a video on Maximum Product Subarray?
NO need to check whether the sum is less than zero or not else do check whether calculated sum is greater than added element or not ? and rest will be same .
grt sir .But this question was asked in my interview but i was not aware of this algo.But i gave a brute force solution by using two loops O(n^2).Here in this algo it is taking linear time o(n). Can we make it to O(log n) by using divide and conquer approach?
if the array is not sorted , we cannot do it in o(logn) . in other way , meaning only binary search will make time complexity of o(logn) and binary search will work only on sorted arrays .
The logic is that you have two variables as you go through the loop. One calculates temp_max and the other max_so_far. As soon as temp_max becomes greater than max_so_far, make max_so_far equals to temp_max. But remember temp_max may not always be greater. And also when temp_max is negative, set it to 0 because you dont want to disturb the previous max by some negative numbers. I hope it helps..
Is Kadane's Algorithm applicable if all the element in the array are positive integer? I have an array like {4,2,1,10,3,5} when I am using this algorithm it return 25 as sum and all the elements . I cannot find any sub array. If I add 10+3+5=18 ,get 18 which is the largest sum in this array also {10,3,5} represent a sub array. For this problem what type of algorithm applicable? Your explanation is very clear and easily understandable. Thank you.
{4},{-3},{-2},{4,-3},{4,-2},{-3,-2},{4,-3,-2}....If u find the sum of the elements of each subarray you will see that (in this case) 4 is the highest..
](http://i.ytimg.com/vi/BOt1DAvR0zI/mqdefault.jpg)
I love the way how innocently he teaches.
Best Explanation of Kadane's Algo I have ever seen. The most important thing that you explained the algo into two parts -
1. Find the greatest sum
2. Find the starting and ending indices of subarray containing the max sum
(2 Line solution ) :-
int Kadane(int[] arr){
int localmax=arr[0];
int globalmax=arr[0];
for(int i=1;i
nice one
What's n here? If it is the length of the array, I get 22 for the above array that Vivekanand has used for the tutorial. Did you try using it before posting the 2-line answer?
Superb solution ☺️😃 enjoy 🤠
Can you explain this solution ?
After wandering in a lot of youtube channels, eventually I've found the best explanation here. Thanks.
Great work man. Brilliant explanation. Please keep doing more videos. hope your channel grows.
The way you explain is so clear. Thanks man.
brilliant explanation! the big thing is he makes it much easier to understand. thanks a lot.
Thank you for explaining the Maximum Sum Subarray algorithm in such an easy way. You are really good teacher! Keep up the good work!!!
the way u explain is crystal clear, thank nu so much @vivek.
Bahut dino se struggle kr rha tha...lekin aaj samaj mei aa gaya. Thanx...
one n only one best explaination of kadane's algo
What if all elements are negative value? How do you dandle max_ending_here < 0 ? How would you track indices?
Above algorithm will not work if all the elements are negative. Please refer : www.techiedelight.com/maximum-subarray-problem-kadanes-algorithm/
This info is very helpful...
Solution is trivial. Return an empty array. Sum of all elements is zero (since there are no elements). 0 is strictly greater than any combination of negative numbers. You could create a subroutine to scan the array and return this result if this is the case. Total running time should be O(2n) which is still O(n).
Then just take the element with with highest value in all negative numbers
@@komuravellyvenky this code also fails if array is [-1]
Best vedio I have ever seen for this solution 👍👍👍👍👍👍
Thank you so much for posting this videos! You have such clear explanations!
Thank you sir for explaining in such a easy way 🙏
You are great Sir! You make so simple with your extraordinary explanation! Thank you very much!!!
Best explanation that i have seen for this algo
Great explanation, I love it. One small simplification may be that max_so_far can be initialized to zero, rather than a[0]. Another advantage of making that change is that if the array is zero-length (size==0) you won't be accessing invalid memory.
you can handle an empty array with a base case that checks for an empty array and simply returns (i.e. if (arr.length === 0) return). If you initialize max_so_far to 0, a test case of [-2] (or any negative number) will fail. I used [-2] as an example because that's the test case I failed on Leetcode lol
awesome explanation sir, very very helpful, thanks a lot for this tutorial 👍👍👍👍🙂🙂🙂🙂
Thank you so much ! your explanation is so helpful.
Nice explanation sir...You have great patience which is must for a programmer.
Regarding this example,we can take a lesser size array to save time.
Vivek, the way you explain is crystal clear by giving examples. Keep up the good work. God Bless.
Very good explanation. You're that favorite teacher kind of person! :)
han rat lo ise
ua-cam.com/video/motMHIXMmzk/v-deo.html
I think for efficient subarray it should be **if(max_ending_here
best explanation among all videos on this topic on youtube. thank you !
Thanks Sanket..!
Nice Video. Well structured. Liked the way you simplified the solution in 2 parts.
1) find the max sum
2) look for index
Nice work thank you.....
Thanks Manoj..!
The second if condition is the core of this algo.
You made things understand easier
can we print the largest sub-array that was found , using Kadane algo?..we can get the end point of that sub-array but how do we get its starting point.
What if we do not have any negative number present in the array?
best explanation of kadane algo
Any idea about how to convert the finding the start index and end index into 2 D array ?
Nice explain sir before watching this video i was confused that what the meaning of this algo but now cleared thanks a lot sir
What will happen if there are no negative numbers in the array?
I've seen this problem posted as a dynamic programming problem on Leetcode. I like this way better though. Is there any argument to do DP over this way?
your understanding of the problem is Bad.....
The way I see the problem is 3 cases : Life Hope and Death.
We'll take 2 sum variables' : prev_sum and current_sum.
Life is when we encounter only positive number: we will update prev_sum in this case
Hope is when we encountered a negative number but that negative number has not made my current sum less than zero so there is still hope that some next number may repair the damage done by the negative number. : we will update prev_sum when current_sum > prev_sum
Death is when the current sum becomes negative .....so now in this case we have re-initialize the starting point for calculating current sum
Below is my smart : : code
public static int findLargestSum(int a[]) {
int end = 0;
int current_sum = 0;
int prev_sum = 0;
while (end < a.length) {
current_sum += a[end];
if (current_sum < 0) { // death case
current_sum = 0;
}
if (current_sum > prev_sum) {
prev_sum = current_sum;
}
end++;
}
return prev_sum;
Set the speed to 1.5, Thank me later:)
Thank u bro :)
Thank u bro :)
Lol ! Thank you bro :)
Thank U Bro :)
i suggest 2.0x
why we equalise the max ending here to zero on second if
If my array is -5 -4 -3-1 -2 will this algo work?
thank you best explanation❤❤
One more observation ... What if the array consists entirely of negative values? This algorithm will report start and end both zero, which is a subarray of length 1. It seems like it may be better, in general, for the result to be reported as a start index and a length (rather than end index). Then the correct answer in this case (all elements negative) is start = zero (or really anything), length = zero. I implemented this here: codepad.org/irM2hs1b
Hi Vivekanan sirji, you are doing a great job..
I have watched some of your other videos too and must say they are simply awesome and to the point..
It will be even better if you could organize your uploaded videos into a playlist, it will direct the users to your other videos.... just a suggestion :)
well said.it ll be great if a playlist is created topicwise.Your tutorial is awesome sir
Yes shobhit i will make it...! Thanks ....!
Yes srinidhi ...will make it..!
you are simple and great....plzz provide some good and tuff DP problems ...:)
What if all the elements in the array is set to 0?
Thnks sir it was very detailed explanation
will this algo works if we have the max sum in -ve itself....i.e if all the elements of the array are -ve, then what to do ?
No this works for everything
Great work Sir. Nice explanation.
Thanks Tanuj.
Will this algorithm work for an input array {5, -2, -1, 3, -4}. Just a second set of eyes to verify we get the result as maximum length of the subarray is 4. Please help!
Good work. Easy to learn. Thank you..
Sir will the algorithm work if the maximum sum is negative?
Hello Sir,
Can you please post video for solution of "maximum/minimum element from each sub-array of size 'k'" in O(n) ?
Thanks in advance.
Best way to explain max sub array prob thanks
Thanks a lot lot sir..you explain us so well
Nice Explanation sir...
Please upload more videos on Dynamic Programming..!!
Very good explanation sir
finally i got the video by which i have understood this concept very easily.
Great Explanation, make some more videos. Thanks
Algorithm tracing != Explaining
What if all values are negative?????
it will return the greatest negative number. So if you have an array = [-6, -5, -20, -1], it will return -1
@@compeng2013 No it is going to return 0, we need to modify the code little bit
Just take the highest elment in the negative no
sir how to approach the algo please teach that not as ratta mar study
if I will take only all elements negative except first then this code will not give the index of maximum subarray you can check it
Great , Great simply you explain I understand, keep doing it , I want learn more algorithm topic probmel
Thanks for explanation
very well done
Thanks Sagar Bhau...!
faulty explanation.. will fail for sample case like [-2 5 -1] where the output of the maxsum with his logic is 3 but it should be 5 actually. *max_so_far* at the starting should be the maximum element of the array.
No it will not fail here, will give 5 as the the max sum
Can you please make a video on Largest subarray with equal number of 0s and 1s with O(N) time complexity and also please make a video on Maximum Product Subarray?
Hi Vivekanand,
Please help me with video to print given matrix in diagonal order
Thanks
Yes i will upload the matrix video very soon..!
sir if whole array is -ve then it won't work?
if the the whole array is -ve then just find the smallest -ve element and its position because that would be largest sum sub array
nice explanation!!
Hello sir, can u make a video on Z algorithm for String search.
Thank you. You made tough problem, easy. :)
NO need to check whether the sum is less than zero or not else do check whether calculated sum is greater than added element or not ? and rest will be same .
Good explanation
grt sir .But this question was asked in my interview but i was not aware of this algo.But i gave a brute force solution by using two loops O(n^2).Here in this algo it is taking linear time o(n). Can we make it to O(log n) by using divide and conquer approach?
if the array is not sorted , we cannot do it in o(logn) . in other way , meaning only binary search will make time complexity of o(logn) and binary search will work only on sorted arrays .
You could divide and conquer in O(nlog(n)) recursively Find max on left, max on right, and find max that crosses the midpoint
Nice, Very Detailed!
Great Explanation.
Where was the explanation of logic in this video... He only puts value and iterate through the loops...Everyone can do that..Please explain the logic!
The logic is that you have two variables as you go through the loop. One calculates temp_max and the other max_so_far. As soon as temp_max becomes greater than max_so_far, make max_so_far equals to temp_max. But remember temp_max may not always be greater. And also when temp_max is negative, set it to 0 because you dont want to disturb the previous max by some negative numbers. I hope it helps..
gandu dekh kahe rha h phr
Longest Palindrome in a string
sir thank you very much.i am from bangladesh.
Is Kadane's Algorithm applicable if all the element in the array are positive integer? I have an array like {4,2,1,10,3,5} when I am using this algorithm it return 25 as sum and all the elements . I cannot find any sub array. If I add 10+3+5=18 ,get 18 which is the largest sum in this array also {10,3,5} represent a sub array. For this problem what type of algorithm applicable? Your explanation is very clear and easily understandable. Thank you.
If array contains all positive numbers, then sum of all elements will be maximum. So the sub array will be the whole array.
After seeing this video, I feel your one of the LC problems god!!!
Nice Work, Thank you Sir
very helpful , thank you
thank you
Great work
you have account in codeforces web site ?
No Mohamed...!
will not work for all negative no in an array
Very Well Explained :)
Please do a video Tutorial on Flatten a Linkedlist, Union of 2 Linkedlist
Yes sure I will do it..!
You didn't explain how the algorithm works. This was simply a dry run which a 12 yo could have done
Sir plz explain dijkstras algorithm with snippet like this sir
Explained well!
please do video , print all different simple cycle in undirected graph . 🙌
yes sure ...very soon..!
Thank you sir 🙏
what about the array.,,,,,, 4 , -3 ,-2 ,,,,, will this algorithm work on it ,,,,,If yes then how ......,,,,PLEASE HELP
{4},{-3},{-2},{4,-3},{4,-2},{-3,-2},{4,-3,-2}....If u find the sum of the elements of each subarray you will see that (in this case) 4 is the highest..
Nice one..Yes need to do like 1.5x or 2x..lol...But great presentation!!
Awesome 👍
Sir you are awesome
Good explanatiin
HI Sir, Can you upload Matrix related java programs with algorithm explanation ... Please sir
Aap direct gfg ka solution mt daala kro plz