Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ("Maximum Subarray" on LeetCode)
HTML-код
- Опубликовано: 31 янв 2019
- Code & Problem Statement @ backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given an integer array, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Approaches Covered:
- Approach 1 O(n^3) Time Solution
- Approach 2 O(n^2) Time Solution
- Approach 3 O(n) Solution (Kadane's Algorithm)
- - - maxSum[i] = max( A[i], A[i] + maxSum[i - 1] )
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech 
Наука
Table of Contents:
The Problem Introduction 0:00 - 0:31
What I Think Immediately 0:31 - 0:55
What Is A Contiguous Subarray 1:00 - 1:52
Jumping To The Brute Force Quickly 1:52 - 2:34
Search Contig. All Subarrays: Birth of Brute Force 2:34 - 3:01
Cubic Time Approach 3:01 - 4:30
Cubic and Quadratic Solutions Search All Windows 4:30 - 4:35
Why The Cubic Solution Is Slower 4:35 - 5:34
Bottlenecks, Unnecessary Work, Duplicate Work 5:34 - 6:04
How To Compute Subarray Sums Better 6:04 - 7:32
Can We Improve To Linear Time? 7:32 - 7:54
Establishing The Fundamental Subproblems 7:54 - 10:32
Establishing Our Fundamental Choice 10:32 - 13:23
Walking Through The Dynamic Programming Table 13:23 - 17:54
We Are Done Filling The Table Out 17:54 - 18:14
The Best Answer To Our Question 18:14 - 18:30
This Does Not Need To Sink In At Once 18:30 - 18:46
Time & Space Complexity 18:46 - 18:58
Wrap Up 18:58 - 19:18
The code is in the description fully commented for teaching purposes.
OMG this break through! You gotta be really serious about creating array's and numeric ranges 😁🤣
yo
The code is not found here github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/MaxContiguousSubarraySum/MaxContiguousSubarraySum.java
@@BackToBackSWE where do i find the code?
Hey I have a problem with the video. Consider the array you used, but only the first 3 numbers in the array (-2,1,-3). While using your approach for the O(n) solution you mentioned the best value at index 2 would be -2. But the answer should be ONE right? Because the best value SO FAR would be the value one. Which is the second number in the array. But you mentioned the best value HAS to involve only either (prev best sum + current element) or only current element...
This video should win Nobel Prize in the "Explain me like I'm five" category. Seriously wow.
haha
@@BackToBackSWE You are amazing, I cant believe I solved the problem easily after watching your explain. Great Job!!
you need to understand not all the users searching for this speak English... or even know anything about CS or IT..., I would love to see him explaining that 1, 2, 3 is continuous or -1, 2, 5
Really surprise your channel is not getting more attention. Sometimes I feel like I have a learning disability but your style of teaching has helped me immensely. Please keep it up!
Hahaha, thanks
The best explanation of kadanes algo on the whole internet. thanks alot.
ye
Never thought of n^3 solution to this problem. The key to understand DP from n^2 is to understand how we got to n^2 from n^3. WOW!
yeah
you are right
The curiosity and excitement in the way you teach took my interest to another level
Fascinating. Check out tomorrow's video. Much excitement there haha.
I am trying to learn from him
I read 5 different articles and watched 3 different videos to try and wrap my head around Kadane's algorithm. This video is the one that finally made it click. Great job, and thank you for sharing!
No one, literally no one can explain THIS BETTER THAN this guy :) The TERM TUTOR is defined for guys like you. Thank You SO much :)
Just want to let you know I truly appreciate the simplification of these types of problems opposed to portraying these algorithms/problems/solutions with a steep learning curve in a demeaning manner. Really wish I saw these earlier, but all I can control is watching these now! Keep up the excellent work and hope you have a great day.
sure and thanks
Such a good explanation, and I appreciate how you walked through the cubic and quadratic solutions as well, it made it easier to understand the linear solution. Thanks!
I really like the icons for different data structures/algorithms that pop up in the videos. I hope they flash up like that in my interviews too.
hahahahahaha, yeah, I made them all by hand. It took like 4 hours to do the whole set.
@@BackToBackSWE Dude MIT/STANFORD should hire you for sure. haha
I am currently enrolled in B.tech programme from India and believe me I had never thought of such tutorials that you make, in one word you are 'GOD'. I have never seen someone make effort to drive in the intuition behind the problem. I have seen a lot of tutorials over the web but again nothing matches this level. I am 100% sure that this channel would grow by 200% in couple of years. I am definitely sharing this to my friends and peers in support of this awesome and yet again awesome channel. Wishing you best of luck in your journey and I will make sure I contribute in several small ways for the growth of this channel.
P.S : I have never written this long comment ever!
hahahahahahahaha, nice, go get em' tiger 🐅🐅
Got an interview tomorrow so I was looking for an explanation to Kadane's. Sleepy af right now and yet I still managed to understand the algorithm thanks to you. God damn man, you really do know how to explain complex subjects so that everyone can understand. Best of luck with your endeavours and keep making awesome videos!
Ye. Go prosper
2 minutes in and I already know this is the best damn explanation I'm ever going to get on this subject. You are wickedly talented at this. Knowing nothing else about you, I would say this is your calling. You're simply too good at it
haha well, I try
God bless this Dude! I was freaking out for job interviews, and thaks to this channel, I am remembering the materials I learned in fresh year!
nice! good luck friend
I have read and watched so many explanations for this problem and I have to say this video is the best. Others seem like they're just repeating someone else without fully understanding the WHY. I could finally understand why the O(n) solution is written that way. Thank you so much!
nice
Thank you so much. I just started codewars and this problem popped up. I've never encountered any dynamic programming before. Watched your video twice and managed to bang out Kadane's Algorithm in python. Onto the next question...
sure
If you are at this video, you will not have to look for other video. You are the master of explaining with ease and breakdown. Thank you!
I struggle with codewars and solving such challenges a lot but I must admit, the way you explain is the best I've seen so far. Thank you for this
Enough is enough. I'm subbing. I love how you break things down so well.
welcome
I must say, this was an amazing watch! It was an AHA moment really, the first time I wrapped my head around the essence of dynamic programming :)
great. glad it helped.
You are one of the best teachers I have encountered on RUclips. You broke the solution effortlessly as if it was an easy one. Thanks for all the effort and keep making videos.
Cheers!
sure
This video right here is GOLD!! it literally forced the concepts of dynamic programming into my skull. I appreciate this.
You are so good at explaining man. You deserve the best.
thx.
Explanation was good enough for me to write the code. I work in the industry, and I was never whiteboard tested, so I have no experience with whiteboard interviews. Now I didn't pick up on how to solve this until I saw you explaining this, and then came up with the code to make it work. I hope in a future interview, the interviewer will help me out a little bit, to get me on the right track if I were to quit my job.
When you say best choice among these two, I remember this dialogue in Captain america: Winter soldier which is like - The best we can do is to start over. It fits well in this solution. XD
haha nice
Honestly, this is by far the best channel I've found to explain these questions. Liked and subscribed, thanks for the awesome content!
all other people I have watched explained the code directly, but you made me write it after this video. Kudos man!
Thanks for the hardwork
You know your channel is super underrated I don't know why but NO one talks with so much depth into how to think! LOVE this video!
thanks, we cookin' up fire out here
Thank you for patiently explaining each step right up to the end. I am sure I will never ever forget this algorithm again.
Blast of a video! Crisp, clear thorough! Love the energy, very helpful
Countless lectures, dozens of RUclips guides, but thanks to you I've finally got it! Thanks
hahahahahah WOOO! Nice. You are born again 👶
absolutely lovely. the best explanation of the ones I've seen on the internet.
thanks
More then Kaden's problem you just explained me dynamic programming in the best way i could ever learn . I guess i can feel dynamic programming now
great
Bro, you are awesome. This is the right way one should explain in to the interviewer in interviews. Never understood Kadane's algorithm before in spite of trying hard. But now I will remember forever.
Keep up the good work.
thanks
I appreciate the amount of effort you put in for preparing each content. The content is amazing and best explanation videos and strategy for interviews. I'm preparing for interviews and I can feel that. Thanks a lot. May you transform more and more lives with your content. Keep posting. :)
Thanks.
I have always known about Kadane's Algorithm and implemented it so many times but never understood the intuition behind it and that it was actually DP. Hats off to you for making me understand this.
I have looked for such an explanation for long.
Thanks for making our lives easy!!!!
Appreciate it.
sure
This video really helps! Thanks for making it :)
sure
I'm so grateful to have discovered your channel. Really appreciate your explanations, thank you.
Teachers are our greatest public servants. Teaching is a calling too. You are the best teacher I have seen on youtube
lol thx
Cool，the clearest explanition both in all the English and Chinese videos. You deserve a lot more subs.
ye
You're a gem of a person! 💓 , I know you've got a new course platform. But you should not stop making more videos, monetise the channel if needed but please keep posting. We love you Ben!
Thanks, yeah I've just been coding prety hard since end of November 2019. Should be less in 3-4 months once we have all languages out for testing. Not sure what content to do back here since it is conflict of interest to continue posting free technical walkthroughs. Might do interviews or something.
Respect from a fellow coder! Your explanation and energy are unparalleled.
thanks and thanks.
I wasn't understanding Kadane's algorithm for the life of me but this video really cleared everything up. Thank you sir!
Appreciate that! I can tell this video has taken a lot of time! The thing I did not understand was the key to this strategy of DP: subproblem should be what is the maximum END of this index instead of what is the maximum has the length of the end at this index. Thanks a lot!
sure
Love your content so much that I search for a concept on RUclips with your channel name to get explanations from you if they are available and then go to other content if your's is not available on that topic. Great work.
really your efforts in making videos reflect, How someone can dislike your video's i mean, they are Exceptional.
just want a request you, "DON'T EVER EVER ...... EVER STOP".
ok
hey ,i saw your video for the first time and trust me it was amazing.I saw 5-10 videos of this topic and lastly landed here.Thanku for such a great content.You are really the best.
Nice - glad we help
I saw this and I right away bought your subscription at backtobackswe.
Hello, your explanation is excellent!
I have a question: How do you get start and end index for the max array?
The code I found in Leetcode does not work when all elements are negative, because they assume the max sum is >= 0.
Please advise, thank you!
not sure why but youtube wouldn't let me post a response to this. I answered a day ago with a really long answer but since it's gone:
Read this first: stackoverflow.com/questions/7778186/how-to-return-maximum-sub-array-in-kadanes-algorithm
Here is a gist:
At any point in time we are expanding a subarray as a candidate that is extending a winning section. All we need is 2 variables to track when we BEGIN expanding a "winner" (the startIndex is reaped this way) and when we expand the subarray to the right (the endIndex is advanced like this).
When we begin expanding a new section then we set a new startIndex.
If this confuses you further continue asking questions.
Absolutely phenomenal explanation for a complex problem!
thanks
You seem to have a youtube video for every question that crushes my soul...
Its even more crushing that after I listen to your video... I implement it, and its 6 lines of code...
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
prev = -2**63
maxSum = nums[0]
for i in range(len(nums)):
prev = max(nums[i],nums[i]+prev)
maxSum = max(maxSum,prev)
return maxSum
@@Hav0c1000 Nice, and consider that procedural complexity of an algorithm does not always correspond to the intellectual rigor required to create it.
Hands down the best and most intuitive explanation of Kadane's algo. Awesome!
thanks
You are my teacher and guide to dynamic programming problems.Now i know what really dynamic programming is.Thanks a lot.
great
what makes you stand out is that you are pretty talented plus you put in a lot of effort in making interactive videos. INSANE
thanks
Great explanation! Kudos for adding table of contents. This is a good video for jumping into DP problems.
ye
Bro your tutorials are awesome! You explain so well , nice make you literally make super complex topic very easy to understand! Feel so bad o found you after so many year :-) kudos and please keep doing the great job !
this was awesome was stuck on this for a good two hours thanks for making it so simple to understand :O)
nice
Love your videos! Keep up the great work!
yessir
Your video about Kadane's Algorithm is the best one ever! Thank you!
Clearly explained! Thank you :)
sure
I really like the way you teach, thank you very much!!
sure
Thank you very much! You've helped me a lot!
nice
Thank you so much, you have no idea how much you impact my life!!
May the internet flourish.
Loved your way of teaching! You earned a follower today sir. Hope you continue to make more such videos.
thanks. Psssssst...you and I...we are gonna change the world :)
@@BackToBackSWE 5 months till I'm going to start looking for jobs, hope to make a smashing entry 🔥😜
THIS VIDEO IS INCREDIBLE! THANK YOU, IT HELPED ME VERY MUCH! YOU ARE THE BEST! 💪
Is the algo you explained for O(n) Kadane's algorithm? Does it only work for sums and not the newfound sub-array itself?
You're doing an incredibly impressive and inspiring job. Thank you for your dedication, and for sharing it with the community. Keep up the excellent work! 🚀
Amazing Amazing. These kind of resources motivate me to do more of CP.
ye
Bought cracking the code interview and never really understood this problem. This was the best explanation I've seen so far, I can even code it by myself
ok, I must say best explanation thus far, thank you for sharing!
sure
Please keep it up.. Your explanation is really helpful to computing science student like me, who is not that smart on solving problems but yet still hoping to challenge myself to make it through the interview! Keep it up man!
ok
Great easy to understand explanations, keep up the fantastic content man :)
thx
This guy is brillant!! Kudos to your effort!! Thank you!
thanks
very concise and thorough explanation. thank you
This is a really good explanation!! Thank you so much
sure
You save me. This is the ultimate solution to my programming assignment. Thank you :)
Absolute legend, clear explanation. Thank you! Subbed.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Thanks man love the energy!!!
sure
this was so good i only watched half and came up with my own implementation that was rly similar to kadanes... good job
great
Man!! you have amazing explanation skills. Thanks for this video.
thanks
The DP solution is amazingly taught!
thanks
Very good explaination and the whole video leads us to think instead of just telling us answer! Thanks!
Hey I was struggling to wrap my head around this problem but this video perfectly clarrified everything!
Really appreciate your efforts to make your audience understand!
sure
I was kind of skeptical at the start because I couldn't understand you well. But after a rewatch, you've cleared up the concept really well. Thanks a ton!
Thank you so much bro, you are the first one explained that why get max between (current_sum+i, i) instead of get max between (current_sum+i, current_sum).
sure
This is a great video. I'd like to see a video on the thought process of how you arrive at the definition for your subproblem
Kadane's is a famous algorithm that someone probably wouldn't get in an interview.
Wow, thank you so much for the video! You are awesome!
sure
Thank you very much! That's a great help for me.
sure, thanks for watching.
Great explanation! Just thank you, man!
Awesome!
U can have all the Phd's in the world but if you lack passion about teaching and what you teach, you wont achieve anything. Thank you sir, for doing what my proffesor dreams of.
Finally understood! Thanks a lot!!!
sure
Kudos. I always had difficulty in understanding this. This video cleared all my queries about this problem.
great
Wow! Thank you very much for the detailed explanation it really helped.
ye
brilliant.. props to the man and his human teaching style
yes
Wowwwwwwwwwwwwwwwwwwwwwwww. God Level Teaching bro.Subscribed your channel in no time after seeing this.
hahah thanks, we have a coding interview class, you should check it out
Awesome and to the point explanation. Great Job!!
thx
Thank you! Best explanation on YT