Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ('Maximum Subarray' on LeetCode)

📹 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] )

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

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.

[bkuls]

This video should win Nobel Prize in the "Explain me like I'm five" category. Seriously wow.

[anarce]

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!

[teamadual]

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

[doublesplitgod]

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

[aliasgar]

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

[james]

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!

[lpatrasco]

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!

[freddie]

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.

[weaponkid]

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!

[sechpham]

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!

[baStYyY]

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!

[niharikapatil]

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!

[nderitupatrick]

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

[ArchitecturalAesthetics]

very concise and thorough explanation. thank you

[prerna]

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!

[cricketjanoon]

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.

[LaughBaron-iuoc]

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

[marcossneijder]

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

[mayurkoli]

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