Kadane's Algorithm - Maximum Subarray (Dynamic Programming)

[@itsjrosa]

I've watched many videos, trying to wrap my head around the explanation of the code. I can finally understand and explain it thanks to you!

[@obsidiangrey1696]

I felt compelled to mention that this approach is (probably) mutating the array. It's been a while since I was working with Java. The approach used in the code in the video would mutate the array in JavaScript, and probably some other languages. That's a little sketchy. It does make the code easy to understand, but there could be issues with that approach. Anything using the array outside of this method would not know that values were reassigned/changed.
Here is a version that doesn't mutate the array (in JavaScript) for anyone interested.
const kadane = (a) => {
let best_sum = 0
let current_sum = 0
for (num of a) {
current_sum = Math.max(0, current_sum + num)
best_sum = Math.max(best_sum, current_sum)
}
return best_sum
}

[@stementhusiast816]

Fantastic visuals and great clarity, this is the best video on Kadane's algorithm I've seen so far. Much appreciated.

[@AlgosWithMichael]

Wow, thanks!

[@aghiadalzein3069]

This is the most simple, directly to the point solution thanks

[@Ivan_lulz]

Thank you. Came from neetcode, I couldn't understand his explanation but this was clearer.

[@40and42]

Hey, I've check lot of videos about Kadane's Algorithm - Your one is the best one! Good job and Thank You!

[@davisgrier5162]

Excellent video. This was the most concise way that I've seen this explained.

[@Tyler_Andrew]

great vid, helped explain it perfectly

[@villurikishore7779]

Great job my friend. I learnt something new today and I didn't have to go through whole lot of other sources or videos to understand.

[@priyanshmathur3010]

Loved the crispness of your explanation....Awesome work!!! :)

[@greg6618]

Great explanation, thanks, Michael!

[@gitanshugupta8556]

Very good work bro, may you get millions of viewers and subscribers

[@AlgosWithMichael]

Haha I wish, that would be awesome!

[@isaac10231]

I think you misspoke about the quadratic time complexity. Bruteforce approach is O(N^3) cause its 3 individual loops

[@marianafernandez523]

Your vide is amazing! Thank you, I think the visual help is really good!

[@chaogui3940]

very well explained, thanks a lot

[@AlgosWithMichael]

Thank you for watching!

[@walnutbread12]

finally i understand this. thank you!

[@NathanSass]

Thank you! Best 8min 24sec of my day so far!!

[@roxanamoghbel9147]

wow this is an amazing explanation

[@MK-iz1gc]

Can I find indexes of Subbaray which is maximum with this algorithm?

[@rotfled]

What if you want to return the indices of the subarray too and not just the max?

[@mcreyfonacier1982]

wait i have a different solution so I did not understand it at first. But it has the same output maybe also time complexity.
I add "i + i+1". It's a little bit complicated to explain but easy to do. Basically I updated all the elements, i + 1 = i + i+1.

[@stardriver8660]

What's the brand of your chair? I will be very appreciative if you could share a link to buy the same one. I really like your chair!

[@posi0504]

why brute force time complexity is O(n^2) not O(2^n)?

[@SimpleSolutions_]

Ive watched this so many times but I cant understand why it works. I get how it works just not why having the max will give you the maximum value of the subarray

[@clementlee8152]

underrated video

[@karthik9354]

Thank you so much...

[@prithvirajrathore4256]

Very nice video . Please make a whole series on algo techniques like dp , backtracking , divide and conquer .
Love from INDIA🗻

[@AlgosWithMichael]

More videos to come!

[@eliy5550]

THANKS SO MUCH

[@sitronco]

great video. Thanks man!!!

[@AlgosWithMichael]

Glad you liked it!

[@gamingKlips99]

Your videos are very helpful. Can you add more graph problem in the graph playlist from leetcode that are important??

[@AlgosWithMichael]

Yea, I will add more

[@CyberMew]

What if we cannot modify the input `nums`? How can this work?

[@AlgosWithMichael]

You could create an array copy

[@solarkenny]

@@AlgosWithMichael call num[i] sum, it's just a variable --
int max = Integer.MIN_VALUE, sum = 0;
for (int num : nums) {
sum = Math.max(sum + num, num);
max = Math.max(max, sum);
}
return max;

[@youcefsaidi5331]

You do not need to modify the array. You can just use variable to keep track of the current max.
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0]
cur_sum = max_sum
for i in range(1, len(nums)):
if ((cur_sum + nums[i]) > nums[i]):
cur_sum += nums[i]
else:
cur_sum = nums[i]
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum

[@mike3498]

holy shit, well done ive subscribed

[@AlgosWithMichael]

Thank you!

[@beboba2498]

It would be easier to understand if you use local and global max

[@bama8127]

this is wrong! maximum sum is 4+3+5+6+1+5=24
or am I missing smth here?

[@shaungannon6571]

He is mutating the array as he progresses through it. Check the initial input array and you will notice that it does not have 4,3,5,6,1,5 in a row. He is using the algorithm to update the entry at each index as he progresses through the array. Hope this helps!

[@AgathiusMusic]

1:35 pointing out a mistake. The time complexity for the brute for solution is not O(N*N) but O(N*N*N) or O(N^3)

[@sandroamaglobeli7281]

I was HERE

[@michieladriaansens5977]

"not to difficult'' he says.. idk what am i missing here because i'm about to throw my laptop out the window!

[@alifyamohamedali1002]

Thank you so much for your comprehensive and concise explanations. I greatly appreciate them. I have been trying to improve my knowledge on graph theory in general. I was wondering if you were going to have a sequel for word ladder to solve word ladder II? Additionally I would love to see you break down 1263. Minimum Moves to Move a Box to Their Target Location Leetcode.

[@AlgosWithMichael]

I will definitely do an explanation on word ladder II!