Kadane's Algorithm to Maximum Sum Subarray Problem

[@larry_in_data1860]

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!

[@benjaminsinanovic4123]

+1

[@UltraB707]

Umm you thought for 1 hr helped you understand quicker ig, I'm watching the video 2nd time still no luck...

[@MohdYusufAbdulHamid]

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!

[@swapanjain892]

Yeah, exactly.

[@benjaminsinanovic4123]

@@swapanjain892 +1

[@huez3n]

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.

[@saurabhverma1381]

You are living in the future, bro.

[@Yazan_Majdalawi]

come revise

[@AnandKumar-kz3ls]

thanks buddy

[@yashp1nth]

according to wikipedia Mr.Kadane came up with the algorithm in less than a minute

[@takharamazanpolat7610]

Surprised pikachu face

[@huaijinruan500]

And it took me less than a minute to copy the solution down (and started to think desperately why it should be the case for 2 hours.)

[@tejassrivastava6971]

@@huaijinruan500 same goes for me

[@sugaku9455]

Lek é bravo menor

[@salvinantonyvarghese6226]

😯

[@sushruttabakade6088]

I was struggling for hours with this algorithm. Thank you for explaining in such detail.

[@genericstospecifics1856]

You are not alone

[@andrefreitas9936]

imagine struggling with Kadane's algorithm 😂

[@thejuniordeputy546]

@@andrefreitas9936 Imagine not able to understand the fact that different people are at different learning phases.

[@andrefreitas9936]

@@thejuniordeputy546 That's me :)

[@xmangle5382]

@@andrefreitas9936 such mediocre mindset and such big ego

[@LetsBeHuman]

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.

[@dulat1]

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.

[@s510533]

Totally agreed with you guys! It took me several times to get it. Thanks again.

[@thelastorca]

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.

[@meditationandrelaxationmus741]

Truly that' s why we need genius to help !

[@fenrir2037]

@@dulat1 That makes much more sense now. I was trying to see how he got [1,-3] as [1,-3] instead of just 1 at 2:17. this helps a lot

[@jessw4195]

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.

[@Monotoss]

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

[@ovebepari6682]

agree

[@bin_california]

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

[@gsmdfaheem]

The best kadane's algo explanation ever!!! ❤️

[@mayankshahabadee8331]

Who dislikes such good content, May god give them brains.

[@amarnathprasad1]

This is the best explanation I could find on KZbin. Thank you so much.

[@naturemagics6267]

The best explanation I have ever seen for kadane's algorithm. Thank you. Its really helpful.

[@sumitbabel5415]

Amazing and simple , clear explanation . Honestly hats off

[@legomgom]

I was working on this problem and didn't understand the core idea until I found your video. Really good job here ! Thanks

[@venkataramanachakravarathu4223]

This is the true explanation of Kadane's Algorithm. Liked a lot

[@ilyashitchens649]

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 ;)

[@maythecodesbewithyou29]

if you have any doubt you can ask me, happy to help a fellow developer

[@shahlazulkarnine9628]

This made my day, the explanation was so thorough and clear, loved it. Thank you !!!

[@dhirajgupta9802]

concise and clear good work man

[@aumkaarpranav8765]

just solved a question, that I couldn't do during the contest, using this algo. such happiness and satisfaction!

[@Tubular-Trev]

You are my hero! thank you for teaching me this stuff. The teachers out here in Kentucky aren't as enthusiastic (university)

[@Jonathan-qz9td]

Haha which part of Kentucky bro

[@Tubular-Trev]

@@Jonathan-qz9td Bowling Green

[@anuj4200]

Wow!! you guys are being taught in universities.

[@CSERISHINANDHA]

@@anuj4200 why you saying so?

[@itsahandle]

@@CSERISHINANDHA our unis don't even do that

[@LetsBeHuman]

Please do more videos like this. You are our saviour.

[@pulak727]

Best explanation of maximum sum subarray problem anywhere on the internet.

[@youknwmyname1323]

You made it so easy to understand. Keep up the good work!

[@egor.okhterov]

You can update max_global in the same way you updated max_current: max_global = max(max_global, max_current)

[@atulwaghdhare]

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

[@ChintanDaveGhost47]

You make the problem so easy to understand. Thank you!

[@rockstar56410]

This is the best explanation I've seen.

[@PopTropicaInnovation]

Best video about this topic. Easy to understand how the algorithm works and also why it works

[@yasararafathn3283]

I wonder how this type of Algorithms are created.Thats awesome.Optimal solution to Maximum Subarray.Thank u Dojo ji

[@7810]

The explanation of the Kadane algorithm is quite clear. Thanks for the lesson!

[@pranaysharma2055]

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?

[@shreevatsalamborghin]

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; } }

[@bsatyam]

I was having such a hard time with this simple problem but you made it so easy! Sleep deprivation is a bitch.

[@bladenjazz]

This was very well explained. Thanks for making this video!

[@DassVeryGood]

Omg you are amazing. I know this is 8 years old but most videos that cover problems with Kadanes algorithm involved don’t explain it well. They either explain why THEY are right, or why the algorithm works for the given problem. This just opened my third eye lmao

[@huaijinruan500]

Thank you so much! I finally understand this stuff after struggling for 2 hours.

[@Flame-hashira-akash]

The best explanation for the maxSubArray question, it's really good that you brought the mathematical proof along with that... :D Really appreciate that.

[@hakimalisami]

Awesome man, you solve the problem with no time.

[@hiepxuan2008]

This video is really helpful, I immediately subscribed you!

[@biplabroy1406]

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.

[@rvscharan4100]

sub array elements should be contiguous so subarray({a,b,c})=(a,ab,abc,b,bc,c). we do not consider ca as it is contiguous.

[@biplabroy1406]

@@rvscharan4100 ooohhh right, how I did this mistake😢. Thanks brother.

[@hanxu6346]

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!

[@ahmedouyahya]

Thank you sooo much and we would like to see more algorithms in this channel. Again thank you soooo much

[@rossinageorgieva9244]

Great! If I ever get my degree in Computer Science, it will be mostly thanks to guys like you!

[@awakashsinha9926]

😂😂 if I ever is hilarious

[@elinorkent7188]

great video us usual. CS Dojo can explain anything to anyone.

[@utkarshmaheshwari7180]

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...

[@aaravpatil2725]

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.

[@dulat1]

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

[@Mrvishalt]

Best and most lucid explanation of Kadane's Algorithm! Simply loved it! :) (Y)

[@chrisalvino76]

very nice. Clear proof, clear code.

[@normalkpopstaner630]

Thank you sooo much . I was really confused before .thanks for clearing my doubt . Thank youuuuu soooo much

[@suganthiarunachalam9077]

Nice explanation. Good job

[@TheChesster777]

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.

[@edgarcn]

It wouldn't happen because the loop begins with the second element i = 1.

[@adrianvdhouten]

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.

[@lostnotfoundyet]

why isn't the max sub array ending in -3, i.e. [1,-3] just [1]?

[@Jamie-bh6mg]

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

[@josephlai7737]

You explained it very well. Thank you.

[@ShabnamKhan-cj4zc]

awsome explanation.Thanks for first explaining the logic and then the algo.

[@nileshmandlik9662]

thank you sir . much love from india

[@sachinsharma905]

Thanks man for the explanation.

[@omerbahat5408]

You've explained it perfectly, thank you so much man!

[@dulat1]

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.

[@dulat1]

By max_ending_here I mean max_current

[@SanketWaghmare]

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)

[@AK09037]

Hold up 2:47, how is max subarray at second index [1,-3] = -2 shouldn't it be just [1]

[@sourashismondal5060]

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 :)

[@bladenjazz]

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.

[@hil449]

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

[@nerdygeek7357]

exactly what I was looking for to solve CF - B. Just Eat It! Thank you DOJO

[@prateekverma8077]

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:)

[@nikhilbhujbal8927]

Very nice explanation 🤘

[@amazingmanish]

Neatly explained. Thank You !

[@newtonsarr1234]

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.

[@sskinedGUY]

In the for loop it should be i < length(A) not i < length(A) - 1

[@shashankcg5029]

Explained really well. Thanks!

[@Enzoerb]

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?

[@mdmesbahurrahman7311]

great tutorial! take love from bangladesh!

[@heginiojrtaeza4187]

awesome explanation. thank you!

[@hakkbak]

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).

[@pranaysharma2055]

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?

[@julianhaurin9658]

@@pranaysharma2055 you add to the local max (4 + 3), not the gobal

[@BeardedBong]

excellent explanation..thanks a lot

[@manikantar60]

Lets assume this is the scenario, 1 2 3 -3 8 , here once we hit -3 , we don't take it and go-ahead, at the moment max_ current is (prev_ maximum_subarray[1,2,3] + current element[8] right? so the result would be 14 , But how this is sub array, here -3 position if left out right?

[@Maxhsynv]

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?

[@narendrakumariitb]

Thank you. Best Explanation

[@hanghu9482]

Thank you, your explaination is clear and precise.

[@cniveditnandakumar4158]

The best tutorial ✅😀

[@ĐàoLong-u7m]

ahhhh, i still dont understand how thiss algo work. Can someone explain it to me?

[@Iamine1981]

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!

[@spicywasab]

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 :/

[@spicywasab]

(I solved it under O(n^2) the first time, but I'm struggling to understand why Kadane's algorithm works.)

[@s510533]

Hi, your lesson is crystal clear, thanks!

[@2bitornot2bit73]

[-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?

[@AnubhavChhabra]

Read the algorithm once again. It works fine with both the test cases u mentioned. Cheers :)

[@praveenchouhan6388]

VERY NICELY EXPLAINED THANKS A LOT!!!!!!!!!!

[@yawar110]

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]

Hello, the sum is 15 because the subarray is [8,-4,4,7]. Hope this still helps.

[@ayushagarwal4247]

@@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?

[@raybastienmayol1261]

​@@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) )".

[@m.usmansohail2853]

sub array of first four elements [8,-4,4,7] gives 15. i know its 3 years old but i still wanted to reply lol and i hope you are doing well.

[@umarhn4922]

nicely explained, i liked how you proved the algorithm.

[@MrTStat]

I still don't get it, someone help me out here even if M is the max what if x is negative? then the sum would be less wouldn't it?

[@shreyajindal4685]

exactlyy

[@giovannimarazzi8737]

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.

[@raymonx4087]

Why the brute force is n^2 not 2^n? Don't we for each element of array need to decide whether include it or not to compute the sum?

[@TheChilllin]

It does not work with [1,2] does it cuz both var are initialized at 1 and the progression makes it go up to 4, or am I going crazy lol

[@marcinkurek2950]

Thank you very much, great and easy explanation

[@PianoOfSouls21]

Awesome video!! Thank you so much for creating this. It really helped me in understanding this problem.

[@maythecodesbewithyou29]

if you have any doubt you can ask me, happy to help a fellow developer

[@fabricator.cap.hill.seattle]

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.

[@SmartProgramming]

helpful tutorial sir, keep it up 👍👍🙂🙂

[@ashinzekene]

Would this work for [-2,3,2,-1,4]?

[@madhukumarv8564]

Nice explanation!

[@artemsvobodin728]

Very clear explanation

[@patrikm8389]

are you sure it's correct? I tried to implement it and with this array [5,4,-1,7,8] it gives me 15 [7, 8] instead of 23 [5,4,-1,7,8] . Looking at your solution seems like you only check if the previous max_current with the current item is larger than the previous max_current, what if you encounter a negative number in the middle that lowers the previous max but after you get higher numbers. Really don't know if I made a mistake or the algo is wrong, here is my implementation: class Solution: def maxSubArray(self, nums: List[int]) -> int: max_current = max_global = nums[0] for i in range(1, len(nums)-1): print('1. max_current', max_current, 'max_global', max_global) max_current = max(nums[i], max_current + nums[i]) print('2. max_current', max_current, 'max_global', max_global) if max_current > max_global: print('current larger') max_global = max_current return max_global

[@jhwang09]

I am trying to understand Kadane's algorithm and specifically about trying to prove it's the case by using contradiction, but I'm not sure I understand how the author came up with the statement: |[T, X]|

[@aryanvardhan809]

Is it possible to get starting and ending indices of the max subarray from Kadane's algorithm?

[@whzd6745]

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

[@josiahroa177]

This algorithm doesn't seem to be working on array input sizes of length 1. For examples [0] or [1]. Should there be a base case for this kind of situation?

[@notlinuxneverdies5846]

is there is a way to calculate O(n) , like can we say O(6^2) equals this many milliseconds? or is it just a parameter to define efficiency in code