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.

@reyou7

5 жыл бұрын

OMG this break through! You gotta be really serious about creating array's and numeric ranges 😁🤣

@BackToBackSWE

4 жыл бұрын

yo

@gondcor

4 жыл бұрын

The code is not found here github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/MaxContiguousSubarraySum/MaxContiguousSubarraySum.java

@harshgupta1999

4 жыл бұрын

@@BackToBackSWE where do i find the code?

@marvelfan5444

4 жыл бұрын

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.

@BackToBackSWE

5 жыл бұрын

haha

@Oda3908

3 жыл бұрын

@@BackToBackSWE You are amazing, I cant believe I solved the problem easily after watching your explain. Great Job!!

@IsaacAlcocer

3 жыл бұрын

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!

@BackToBackSWE

5 жыл бұрын

Hahaha, thanks

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!

@BackToBackSWE

5 жыл бұрын

yeah

@maythecodesbewithyou29

4 жыл бұрын

you are right

The best explanation of kadanes algo on the whole internet. thanks alot.

@BackToBackSWE

4 жыл бұрын

ye

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

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!

The curiosity and excitement in the way you teach took my interest to another level

@BackToBackSWE

5 жыл бұрын

Fascinating. Check out tomorrow's video. Much excitement there haha.

@maythecodesbewithyou29

4 жыл бұрын

I am trying to learn from him

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.

@BackToBackSWE

3 жыл бұрын

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!

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!

@BackToBackSWE

4 жыл бұрын

Ye. Go prosper

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!

@BackToBackSWE

5 жыл бұрын

hahahahahahahaha, nice, go get em' tiger 🐅🐅

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

@BackToBackSWE

4 жыл бұрын

haha well, I try

You are one of the best teachers I have encountered on KZread. You broke the solution effortlessly as if it was an easy one. Thanks for all the effort and keep making videos. Cheers!

@BackToBackSWE

4 жыл бұрын

sure

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

all other people I have watched explained the code directly, but you made me write it after this video. Kudos man!

@BackToBackSWE

2 жыл бұрын

Thanks for the hardwork

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!

@BackToBackSWE

4 жыл бұрын

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!

@BackToBackSWE

4 жыл бұрын

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

@BackToBackSWE

4 жыл бұрын

sure

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

@BackToBackSWE

4 жыл бұрын

great. glad it helped.

Honestly, this is by far the best channel I've found to explain these questions. Liked and subscribed, thanks for the awesome content!

This video right here is GOLD!! it literally forced the concepts of dynamic programming into my skull. I appreciate this.

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.

@BackToBackSWE

5 жыл бұрын

hahahahahaha, yeah, I made them all by hand. It took like 4 hours to do the whole set.

@Natasha-ux5pm

4 жыл бұрын

@@BackToBackSWE Dude MIT/STANFORD should hire you for sure. haha

Enough is enough. I'm subbing. I love how you break things down so well.

@BackToBackSWE

4 жыл бұрын

welcome

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!

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

@BackToBackSWE

4 жыл бұрын

ok

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.

@BackToBackSWE

4 жыл бұрын

thanks

You are so good at explaining man. You deserve the best.

@BackToBackSWE

4 жыл бұрын

thx.

Thank you for patiently explaining each step right up to the end. I am sure I will never ever forget this algorithm again.

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!

@BackToBackSWE

5 жыл бұрын

thanks, we cookin' up fire out here

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.

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.

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!

@BackToBackSWE

4 жыл бұрын

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.

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

@BackToBackSWE

4 жыл бұрын

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

@BackToBackSWE

4 жыл бұрын

great

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.

@BackToBackSWE

4 жыл бұрын

Nice - glad we help

I saw this and I right away bought your subscription at backtobackswe.

Respect from a fellow coder! Your explanation and energy are unparalleled.

@BackToBackSWE

4 жыл бұрын

thanks and thanks.

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

@BackToBackSWE

5 жыл бұрын

haha nice

Countless lectures, dozens of KZread guides, but thanks to you I've finally got it! Thanks

@BackToBackSWE

5 жыл бұрын

hahahahahah WOOO! Nice. You are born again 👶

Blast of a video! Crisp, clear thorough! Love the energy, very helpful

absolutely lovely. the best explanation of the ones I've seen on the internet.

@BackToBackSWE

5 жыл бұрын

thanks

Cool，the clearest explanition both in all the English and Chinese videos. You deserve a lot more subs.

@BackToBackSWE

4 жыл бұрын

ye

I have looked for such an explanation for long. Thanks for making our lives easy!!!! Appreciate it.

@BackToBackSWE

4 жыл бұрын

sure

I wasn't understanding Kadane's algorithm for the life of me but this video really cleared everything up. Thank you sir!

Teachers are our greatest public servants. Teaching is a calling too. You are the best teacher I have seen on youtube

@BackToBackSWE

3 жыл бұрын

lol thx

Hands down the best and most intuitive explanation of Kadane's algo. Awesome!

@BackToBackSWE

5 жыл бұрын

thanks

Love your content so much that I search for a concept on KZread 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.

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

what makes you stand out is that you are pretty talented plus you put in a lot of effort in making interactive videos. INSANE

@BackToBackSWE

3 жыл бұрын

thanks

Your video about Kadane's Algorithm is the best one ever! Thank you!

I'm so grateful to have discovered your channel. Really appreciate your explanations, thank you.

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!

@BackToBackSWE

4 жыл бұрын

ok

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!

@BackToBackSWE

4 жыл бұрын

sure

You are my teacher and guide to dynamic programming problems.Now i know what really dynamic programming is.Thanks a lot.

@BackToBackSWE

4 жыл бұрын

great

This video really helps! Thanks for making it :)

@BackToBackSWE

5 жыл бұрын

sure

Absolutely phenomenal explanation for a complex problem!

@BackToBackSWE

4 жыл бұрын

thanks

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)

@BackToBackSWE

4 жыл бұрын

nice

Thank you so much, you have no idea how much you impact my life!!

@BackToBackSWE

4 жыл бұрын

May the internet flourish.

THIS VIDEO IS INCREDIBLE! THANK YOU, IT HELPED ME VERY MUCH! YOU ARE THE BEST! 💪

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!

You save me. This is the ultimate solution to my programming assignment. Thank you :)

Amazing Amazing. These kind of resources motivate me to do more of CP.

@BackToBackSWE

4 жыл бұрын

ye

The DP solution is amazingly taught!

@BackToBackSWE

5 жыл бұрын

thanks

Hey I was struggling to wrap my head around this problem but this video perfectly clarrified everything!

Great explanation! Kudos for adding table of contents. This is a good video for jumping into DP problems.

@BackToBackSWE

4 жыл бұрын

ye

This guy is brillant!! Kudos to your effort!! Thank you!

@BackToBackSWE

4 жыл бұрын

thanks

ok, I must say best explanation thus far, thank you for sharing!

@BackToBackSWE

4 жыл бұрын

sure

We need teachers like you ♥

@BackToBackSWE

4 жыл бұрын

thanks.

You seem to have a youtube video for every question that crushes my soul...

@Hav0c1000

4 жыл бұрын

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

@BackToBackSWE

4 жыл бұрын

​@@Hav0c1000 Nice, and consider that procedural complexity of an algorithm does not always correspond to the intellectual rigor required to create it.

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! 🚀

I really like the way you teach, thank you very much!!

@BackToBackSWE

4 жыл бұрын

sure

Very good explaination and the whole video leads us to think instead of just telling us answer! Thanks!

Incredible explanation that I have seen on this topic. Love it.

Thank you! Best explanation on YT

Really appreciate your efforts to make your audience understand!

@BackToBackSWE

5 жыл бұрын

sure

Loved your way of teaching! You earned a follower today sir. Hope you continue to make more such videos.

@BackToBackSWE

5 жыл бұрын

thanks. Psssssst...you and I...we are gonna change the world :)

@dhruvkaushal8708

5 жыл бұрын

@@BackToBackSWE 5 months till I'm going to start looking for jobs, hope to make a smashing entry 🔥😜

this was so good i only watched half and came up with my own implementation that was rly similar to kadanes... good job

@BackToBackSWE

3 жыл бұрын

great

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

@BackToBackSWE

4 жыл бұрын

sure

I am commenting first time on any of the videos and these are the best tutorials , i have ever seen.

@BackToBackSWE

4 жыл бұрын

great and thanks - appreciated

One of my fav channels. I wish you had received more attention,

Man!! you have amazing explanation skills. Thanks for this video.

@BackToBackSWE

5 жыл бұрын

thanks

Best explaination which gave me intuition of how to thought even if I forgot this algo🔥

Clearly explained! Thank you :)

@BackToBackSWE

4 жыл бұрын

sure

Wowwwwwwwwwwwwwwwwwwwwwwww. God Level Teaching bro.Subscribed your channel in no time after seeing this.

@BackToBackSWE

4 жыл бұрын

hahah thanks, we have a coding interview class, you should check it out

The best explanation of kadane's algorithm !

Way better than some professor from college. Keep going. You have all my support.

@BackToBackSWE

4 жыл бұрын

ok

Thank you so much for the video. Your explanation was the best for me than other sources

Just the words "Kadane's Algorithm" should already won you a medal, not to mention the expended explanation! Kudo! A O(n^2) can still pass LeetCode test if you memorize the previous result. But nothing beat O(n)!!

Kudos. I always had difficulty in understanding this. This video cleared all my queries about this problem.

@BackToBackSWE

3 жыл бұрын

great

Im crying, thank you soo much, I was afraid of the word 'dynamic programming' . It feels like you just walked me through my own thinking process and improved it. I needed to know if there are any tips for preparing in c++ for the big four? Thank you 🤓😊

@BackToBackSWE

4 жыл бұрын

Chil - ur good. And no I have none.

I am trying to come up with the recurrence of this problem and saw your video on leetcode. the explanation is super clear. thanks !!

@BackToBackSWE

5 жыл бұрын

nice

brilliant.. props to the man and his human teaching style

@BackToBackSWE

3 жыл бұрын

yes

thanks for helping in digesting the algorithm ,now it feels complete

wow this is an amazing explanation of kadane's algorithm

OMG BEST video on KADANE's algorithm.TYSM

@BackToBackSWE

4 жыл бұрын

thanks and sure

smoothly explained. I Always find the best explanation of leetcode problems in your videos. Keep up the great work (y)

best explanation I ever heard, super great.

Thank you very much! You've helped me a lot!

@BackToBackSWE

4 жыл бұрын

nice