You are such a great lecturer, it took me 1 hour to think about it but ended up with frustration, but you just make me understand within 10 minutes, thank you!
This is actually the best explanation of Kadane's algorithm I have seen. I kept asking myself why is this algorithm not very intuitive; with your explanation, it is now.. thanks!
5:34 - 8:01 - It differentiates you from other guys. You are the only one here explained why it works. But some how for me, I watched it 4 times and I still don't get it. I will watch it few more times. Edit update: Ok , I got it now.
It was hard for me to get it too for quite a time but finally I get it. I think what people often confuse is the meaning of max_ending_here. The variable max_ending_here at some index i does NOT mean the maximum subarray sum that can be chosen between 0 and i. It only means the maximum subarray sum that actually ends at that i meaning includes that index i in the end. For example, for an array {2, 3, -7, 1, 2} at the last index which is i=4, max_ending_here is not 5, it is 3. Because it has to END at that index. If you got this then watch the video one more time and it should be clear.
Its like, instead of looking at your life time after living it and finding the best parts by passing through it AGAIN "O(n squared)", you use smaller chunks of your history that you have lived so far and update the best part WHILE LIVING IT. By the time you die, you will know the best part "O(n)". Something to think about: You are already programmed efficient, coz you follow the second way by nature.
Summary : The brute force method works by finding the maximum subarrays ending at all n indices and comparing them. Kadane's Algorithm principle, 3:42 : Maximum subarray ending at the (i)th index is either the current element,A[i] or the current element combined with the maximum subarray ending at the (i-1)th index. PS : Just leaving this so I can revise later if needed.
I also agree with "5:34 - 8:01 - It differentiates you from other guys" opinion. You are way way better guy than guys who just 'throws code and say it works'. Knowing much doesn't mean one is a great teacher. The one that I admire is the person like you who teaches and explains so well for others to understand easily. Lots of appreciation Man. I hope you upload more of these algorithm explain series
Appreciate the effort, but i feel this part was obvious (if M > 0, you take M+x, otherwise you take jus x), maybe just because me doing years of leetcode already, lol
Thank you so much. The way you explain it makes it make so much sense. I could not understand how something so simple worked, but how you explained the principle, the core, of Kadane's Algorithm clicked for me.
The explanation is really clear, I've been stuck quite a few hours in solving a problem involving Kadane's algorithme and coudn't visualize it. thanks from France ;)
Here there is no checks for whether this will take the subarray as contiguous or not... Test with this array:- -2,4,2,-1,5 According to your approach at index 3 it will keep max_current as 6 and at the index 4 the max current will become 11 which isn't correct I guess...
At index 3(where value is -1 in your example) max current will be 5 bcoz max_current = Max(-1, 4+2+(-1)) = 5 and at index 4 the max_current = Max(5,5+5) = 10. check your code the algo works fine.
At index 3, max_ending_here becomes -1. max_current is still 6. Then at index 4, max_ending_here becomes 5. max_current=max(max_current, max_ending_here) which is 6. So no problem
Because we're looking for the max sub array which ends at -3, so it must include -3. Your answer of [1] is the maximum sub array of [1, -3], but it does not end at -3, it ends at 1
The best explanation for the maxSubArray question, it's really good that you brought the mathematical proof along with that... :D Really appreciate that.
For those of you who are still confused, you are most probably missing the meaning of the variable max_ending_here. For example, for an array {-1, 5, -2, 4} when i=2, we are only considering the first 3 elements so far. So the array part we are looking at is {-1, 5, -2}. So what is max_ending_here at this point? It is not 5. It is 3. Because max_ending_here refers to a subarray with a maximum sum that actually ends at that index itself. So the answer is {5, - 2} with sum of 3. So max_ending_here has to END at that index meaning its last element has to be at that index i where you are currently in the loop. If you get it watch the video again and it should be clear.
Kodane's Algo Thank you so much for the explaining. Basically: Brute Force helps but takes a long time. So we choose to find and pick the local maxima among the array while also find the global maxima. By this way we also can get only the global maxima. Man this feels like apply the Maths I learnt as a child
max_current should be initialized at 0, since if say, an array contains [5, 3, -2] and we initialize current_max to be A[0] and we do the current_max = max(current_max, current_max + A[i]) current_max will be 10 instead of 5, and there's no sum that can add to 10 in the array.
Thank you for the detailed explanation. It started making a lot of sense when you drew out the values in a table. Though to make it work, I had to initialize my max_current and max_global as 0 instead of A[0]. Subscribed!
Guys if you are getting wrong answers for specific inputs then. Try this: there is small logical error. Consider adding new variable maxcurrent1 inside the function. Initialize it with the max value obtained maxcurrent1=max (a[I] , a[I]+maxcurrent) Which will be compared with maxcurrent. Which is shown to be initialized with a[0]. Only update if maxcurrent1 is greater than old maxcurrent If(maxcurrent1>maxcurrent) { maxcurrent=maxcurrent1; } If(maxcurrent>maxglobal) { maxglobal=maxcurrent; } return maxglobal;
It's common sense why Kadane's Algorithm works. If you are picking the maximised "sub-array total" after each element, then there's no 'room' for other possibilities which have a greater sub total (unless the single new element is superior, in which case we take that instead).
what happens for this array [3,2,-1,3,-3].. observe my case below index --- - 1 2 3 local----- 3 5 4 5+3-->which is wrong it should be 4+3 global--- 3 5 5 what happens in such cases?
Thank you! If you had trouble understanding the meaning on sub, think of sub_string, where we get a portion of a string by specifying certain indexes of characters we want to extract from the string. The sub array has the same concept.
Man u r so great i couldnt write on my own this algo before watching your vid but after it your algo comes to my mind and i can write it on my own thanks:)
what happens for this array [3,2,-1,3,-3].. observe my case below index --- - 1 2 3 local----- 3 5 4 5+3-->which is wrong it should be 4+3 global--- 3 5 5 what happens in such cases?
how about this? What about this ? O(n) solution without using kadane's algorithm isnt it..? class Solution { public int maxSubArray(int[] nums) { // ans is the final result and currentsum is the sum of current window int ans = 0, currentsum = 0; //intialize the current window to the first element also the final ans currentsum = ans = nums[0]; for(int i=1;i than the existing res then update the current sum if(currentsum + nums[i] > nums[i]) { currentsum+=nums[i]; } //else change the window starting pos to the current element since the result is to be contingous. else { currentsum = nums[i]; } //update largest result after every iteration. ans = Math.max(ans,currentsum); } return ans; } }
I gave a Thumbs Up for this video. I did not get the proof towards the end of the "Why Does Kadane's Algorithm Work?" section, math proofs aren't my strong point, but I still liked the rest of the video.
Start programming early. You can make huge bucks by the time you end high school. You can use that money to buy new games or xbox or play station etc. :P
You can earn money from programming competitions or hackathons etc. Also there is freelancer or upwork. As a kid, you dont really need money so you can make projects for free at least the first few and then you have a client base to earn money. Also as a kid you can offer cheaper services coz money is not a dealbreaker for you as you have your parents even if you dont get money from your freelancing or hackathons etc. But of course that would take away all the fun of being a kid I guess.
Don't listen to them kid. Do whatever you like rather than learning programming for money 'cz every other person is for making money in the software industry and no doubt they are making a good sum but to stand out from others you need to have it as your passion. In simple words don't study anything for money, study to improve yourself, to fulfill your hunger of knowledge and curiosity. Don't try to have fake hunger for anything.
@@blasttrash Hahaha I love how you just translated the ultimate goal to something kids can relate to :) :). "so you can buy more Lego and Lego games on your phone"
Thanks for posting a very neat explaination (thumbs up for that). I think I might have missed something here... when A = [ 8, -4, 4, 7, -1, -10 ], the code returns 15 as global max, which means its adding 8 and 7 and these two values are not subarray. I was expecting it to return 4 + 7 = 11 as global max. Please correct me if Im wrong.
@@raybastienmayol1261 A = [1,-2,3,4,-4,5] considering this array as input, the code returns 7 as answee (i.e. [3,4]), but the answer should be 8 (i.e. [3,4,-4,5]. Can you explain me this?
@@ayushagarwal4247 Your code might not be checking the last element. Taking the pseudocode in the video and turning it into python, it made sense for me to remove the "-1" in the for statement. So I was using "for i in range(1, len(A) )".
But what about something like: [6, 7, -1, 5, -10]? [6, 7, -1, 5] is the max subarray But [6, 7] sum > [6, 7, -1] sum > [-1] sum And [6, 7, 5] is not a possibility Therefore, wouldn’t I need to compare those 3 things? From the beginning of the max subarray, to X, the current maximum subarray and only X?
This algo does not work. Consider [3, -2, 4, 3, -1], the max sub-array should include the first two elements since they contribute +1. His ending example was a naive [-2, 4, 3, -1] without interleaving positive/negative numbers.
The correct solution was published in the Programming Pearls book, and at stackoverflow.com/questions/3763619/programming-pearls-finding-sub-array-with-max-sum maxsofar = О maxendinghere = О for i = [0. n) { maxendinghere = max(maxendinghere + x[i], 0) maxsofar = max(maxsofar, maxendinghere) } The critical line is the first max() operation within the loop cannot just compare maxSoFar, which is named as max_current in this RU-vid video, against the current newly encountered element. It needs to compare less aggressively against just zero, to accommodate for the case that previous previous numbers could still have positive contribution and cannot be dismissed by just comparing against a[i].
thanks for the heads up! I had a similar codility challenge of finding the slices (P,Q) of an array that has minimal average, and finding its index P. I solved it but my performance is still O(N**2), and I believe tweaking your approach can help me lower my runtime to O(N) by using running sums for the average. thanks!
Currently doing the selections for france's computing olympiad. Did the first "exam" a week ago, doing the second one tomorrow. I also had something pretty similar, basically removing consecutive values of an array so that the average of the resulting values is the lowest. I found this algorithm a few days ago while I was reading "Competitive Programmer's Handbook" (a free book on the internet). I'm pretty sure I can tweak this solution too, but I know I wouldn't have been able to find it under reasonable time :/
1:34 please explain why brute force solution has the complexity of n^2,,,, In my logic in brute force we are looking in every subset of the set so there are 2^n subsets. Subarray( {a, b, c} ) = (a, b, c, ab, bc, ca,abc) 7 elements... In this logic the order should be O(2^n).. I know there are some mistakes done by me. Please let me know where I doing the mistake.
For list of length 2 this would provide wrong output. I am sure many must have added this correction in previous comments. The for loop should have range from 1 to len(list)
Sir, it's been a while now since you posted your last video. We all really love the way you teach. Atleast give us a reason for not posting videos anymore.☹
You could keep the previous max sum and at each iteration check with previous max sum is positive. If positive, you add it to the current, if negative, you don t add it.
there is an alternative optimal solution, it's using prefix sum. You first get the prefix sum array of your given array, and then just subtract the largest with the least. That would take n runtime
If I'd know the vector have at least one positive number i would do it a little different using 3 subarrays. First I would search for the first number >= 0 and set as first of the "maximum subarray". Next I analise if the next number is positive if yes i add to subarray if not i hold in a "negative subarray" and keep adding to it as i find more negatives. The moment i find a positive number i hold in a "positive subarray" and keep adding to it until i find a negative number. when i have set a negative subarray and a positive subarray i sum them. If they result >=0 then i add both to "maximum subarray". Next only repeat.
[-2,3,2,-1,8] vs [-2,3,2,-16,8] will give wrong results: not taking into account the -1 or -16 value before the 8 will give wrong answers (the algo clearly skips the values in between current_max and a[i]) - am I missing something here?
your code doesn't return 0 if all elements of the array are negative. my solution on codewars: var maxSequence = function(arr){ var runningMax = 0; var maxEndingHere = 0; for (var i = 0; i < arr.length; i++){ maxEndingHere += arr[i]; if (maxEndingHere < 0) maxEndingHere = 0; if (runningMax < maxEndingHere) runningMax = maxEndingHere; } return runningMax; } returns 0 (empty sub-array) if all elements are negative.
I'm still confised about intuition behind it. You just directly started asking "what is maximum sub-array ENDING at this index?", but what I was thinking before was "what is maximum sub-array STARTING at this index?" which took me to wrong approach. So what is the reason behind it?
You described the recurrence relation , but what if the max subarray of the smaller sub problem is not he last part of that sub problem , instead it is somewhere in the middle of the subproblem . I dont understand how this algorithm is DP . Because if I try to solve it recursively, there is no overlapping subproblems. If anyone knows , please feel free to explain :)
This is one year later but I believe what you need is this. At each step of the algorithm you are deciding what is the max sub array that ends at the current index. As he said, it will either be the current index only, or the precious index's max sub array plus the current index.
i think you meant 'if its in the middle of the array'. If the best is in the middle we're gonna find it during the for loop and we're gonna combine it with the best subarray sum to its left. Btw this is not a dp problem, this is greedy imo because you can solve this problem using prefix sum and a greedy approach
he used contradiction to prove the algorithm, if you have a small background on proof techniques you can easily understand what he is talking about . also its a very easy and intuitive algorithm, i dont know why many people dont understand it...
old question but something like this is working for me, where (l)eft and (r)ight are the starting and ending indexes. def maxSubArray(nums: List[int]) -> List[int]: curSum, maxSum = 0, -inf l, r = 0, 0 for i,n in enumerate(nums): if n > curSum+n: curSum = n l = i else: curSum += n if maxSum < curSum: maxSum = curSum r = i return [maxSum, l, r]
@@baiano360 Your code doesn't get the correct indices. For example on test case: [5, 4, -1, 7, 8] Your code returns 0 as start index, and 3 as end index. The expected should be 0 as start, but 4 as end. (The max subarr is the entire input array; sum = 23)
