Kadane's Algorithm - Maximum Subarray (Dynamic Programming)
Vložit
- čas přidán 20. 04. 2021
- Maximum subarray is a popular LeetCode interview questions asked at Microsoft, Amazon, Apple, LinkedIn, ByteDance, Google, Adobe, and several other top tech companies. This problem is solved in the most efficient way using dynamic programming with an algorithm known as Kadane's algorithm.
Kadane's algorithm finds a contiguous subarray with the largest sum in linear time. Using this algorithm, as we iterate through our array, we compute the max subarray at each step using the following recurrence relation; current is equal to the max between the current and the current plus the previous. Since we overwrite the formula values with the array we are given, the algorithm provides a constant space complexity in addition to the linear time complexity.
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
🔗 Social 🔗
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos - Věda a technologie
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!
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
}
Fantastic visuals and great clarity, this is the best video on Kadane's algorithm I've seen so far. Much appreciated.
Wow, thanks!
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.
Excellent video. This was the most concise way that I've seen this explained.
Hey, I've check lot of videos about Kadane's Algorithm - Your one is the best one! Good job and Thank You!
Loved the crispness of your explanation....Awesome work!!! :)
Great explanation, thanks, Michael!
Thank you. Came from neetcode, I couldn't understand his explanation but this was clearer.
Your vide is amazing! Thank you, I think the visual help is really good!
This is the most simple, directly to the point solution thanks
wow this is an amazing explanation
finally i understand this. thank you!
great vid, helped explain it perfectly
very well explained, thanks a lot
Thank you for watching!
Very good work bro, may you get millions of viewers and subscribers
Haha I wish, that would be awesome!
great video. Thanks man!!!
Glad you liked it!
THANKS SO MUCH
underrated video
Thank you so much...
Can I find indexes of Subbaray which is maximum with this algorithm?
Thank you! Best 8min 24sec of my day so far!!
What if you want to return the indices of the subarray too and not just the max?
I think you misspoke about the quadratic time complexity. Bruteforce approach is O(N^3) cause its 3 individual loops
holy shit, well done ive subscribed
Thank you!
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!
Your videos are very helpful. Can you add more graph problem in the graph playlist from leetcode that are important??
Yea, I will add more
Very nice video . Please make a whole series on algo techniques like dp , backtracking , divide and conquer .
Love from INDIA🗻
More videos to come!
why brute force time complexity is O(n^2) not O(2^n)?
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.
What if we cannot modify the input `nums`? How can this work?
You could create an array copy
@@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;
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
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
It would be easier to understand if you use local and global max
I was HERE
this is wrong! maximum sum is 4+3+5+6+1+5=24
or am I missing smth here?
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!
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)
"not to difficult'' he says.. idk what am i missing here because i'm about to throw my laptop out the window!
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.
I will definitely do an explanation on word ladder II!