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

Key Takeaways

so today we have the question max contiguous sub-array some so in this question what we're given is we're given an array with positive and negative values so I've numbered the indices here for you to see we go from indices 0 to embassy 8 and our question is what contiguous sub array of the array is going to have the largest sum so whenever we get a question that asks us for the maximum of a array or a group of items sometimes I think heap if I'm thinking of quantities or largeness of value but sometimes I think of dynamic programming I think of using dynamic programming to find an optimal global solution based on smaller subproblems I just want you to keep both of these in mind as we parse what this question means when we get first get this question as if we've never heard it we get this array first of all I want to address what is a sub array what is contiguous what does that mean so what does contiguous mean so contiguous means we do not have a break in a snippet that we take from the array so it would kind of look like this so that is a contiguous sub array negative 2 & 1 is a contiguous sub array negative 2 1 & 3 is a contiguous sub array negative 3 4 & 1 is a contiguous sub array do you see how this line that I drew does not break that is what contiguous means if I do this if I try to take a subset of this overall array with negative 2 1 4 and negative 1 do you see how we break here that makes it non contiguous so what it has to be is contiguous we need contiguous sub arrays and we want the continued sub array with the largest sum so how do we go about this question so I want you to notice what your mind did when I introduced the idea of sub arrays you saw me enumerate the sub arrays and maybe your minds might have went along in a new the rest of the subarrays maybe you started thinking what are all the possible subarrays I could do and when we get a question like this the max continuous subarray some you might be thinking let's take all of this sub arrays and see what their sums are and find the one with the maximum sum this is the straightforward solution if I was an interview I would immediately say this is what my mind is going straight towards this is the brute force and this is what I immediately think so this solution is going to bring us to a cubic time and a quadratic time solution so let's look at the cubic time solution first and by the way the code is in the description I think the code will explain it better than this video could even explain this problem this video is just a walk through I want you to go through but I think you'll learn a lot more from seeing the code for at least the naive approaches but the final linear time solution might need some explanation here code is there if you need it let's look at the approaches now let's look at the first approach so what we can do is we could do an exploration of all of the contiguous sub arrays so what I do is I plan to myself at the first item I have a left and I have a right and I explored I plant at a left I explore Explorer window Explorer window Explorer all the windows to the end when I hit the end I close the left and then I bring the right back and then I keep exploring and then I hit the end and then I close in the left and then I bring the right back so that is our approach to look at all of the windows so what we're going to do is something like this I will get the sub array of negative two and I'm going to find the sum in here the sum of this sub array is just going to be negative two that's pretty straightforward and then we're gonna look at this sub array okay we look at the sub array of negative two and one the sum of that sub array is negative 1 so this subarray some beats the sum of just negative two so the new best subarray sum would be so the new best subarray sum would be that sub array of some negative one we take another suffering and notice our left bound is still the first item we haven't changed our left bound because our right bound is not at the end of the array for this sub array the sum is going to be negative 4 does that beat the best some we've had it does not be or the best somebody that it does not be negative 1 this is how the cubic and the quadratic solutions will do things they're going to look at all of the windows so the difference between the cubic and the quadratic solution is the cubic solution what it's going to do is it's going to get the sum for this sub array it's negative 2 and then what a cubic solution will do is it says I want the sub array for this window how do i compute it the cubic solution will go all the way back to the beginning and say negative 2 plus 1 and then we'll have negative 1 and then we're going to want the next window and what our cubic solution is going to do it's going to go all the way back to the left bound all the way back to the negative 2 and is going to say negative 2 plus 1 plus negative 3 and we're going to get negative 4 so do you see the problem there do you see how we're going to take a sum here and then we're gonna go all the way back we're gonna take a sum here in here and then we're gonna go all the way back and then we're gonna take a sum here here and here we're going to be repeating work whenever we're trying to optimize an algorithm we think of the bottlenecks the unnecessary work and the duplicate work so this is from cracking the coding interview it's bu d stands for bud bottlenecks unnecessary work and duplicate work we're duplicating work by finding a sum for every new sub array but the problem is we already have information about a sub arrays some do you see how to suffer it just negative 2 if we know that is a sum of negative 2 why would we take the whole subarray sum for these two items why not just add on the right bound that we just added our improvement to turn this into a quadratic time algorithm is that we notice to get the sum advancing between windows all we need to do is tack on the right bounds because we already have the sum for everything preceding that so what we do is we get the sum for this window and then the sum for this window is going to be the sum for this window plus the item we just added so now the sum for this window is just negative one and now we want the sum for this window but we already have the sum for this window we just added one item we just add negative three it's a negative one the sum for this window is negative four and now we want the sum for this window we just added four we already know the sum to the window preceding it we've already done that work we don't want to duplicate work so we add 4 to negative 4 from the previous sub window so what we get is 0 and like this we eliminate that inner for loop again the code is in the description if you want to see that we eliminate that innermost for loop and we take our time to quadratic time and that is how the naive solution works oh and that is how the naive solutions work the both the cubic and the quadratic time what they're going to do is they're going to search all the sub windows and the way we approve between them is how we find the sub between the sub windows so how do we turn this into a linear time algorithm because whenever I see an array problem I always try to think of ways we can solve the problem in linear time so what we need to introduce ourselves to what we need to re shift our thinking to is we need to start thinking in terms of dynamic programming and subproblems ok so now what we're going to do is we're going to look at the dynamic programming approach and the thing about dynamic programming is it's a very tricky topic every single problem has a different way these subproblems break down and relate to each other but as soon as you see these sub problem as soon as you see how they relate to each other it becomes very straight forward so there is a code sample in the description that runs in linear time and constant space here we're going to use linear space so that we can see these subproblems and we can see how everything works but this can be done in constant space and the most efficient solution is in the description so what we need to understand is whenever we build a dynamic program table whenever we do dynamic programming it is not about memorizing what the table is about it's about knowing the subproblems what are the subproblems that is our question so when I am at this indicee my question right here is what is the maximum continued subarray sum if I end at the index zero if my sub array if the rights bound ends at index zero what is the maximum contiguous sub array some our sub problem here if my sub array were to end at to the index 3 what is the best that I can do in terms of subarray sum so the different sub arrays that end that's the index 3 look like this so these are all of the contiguous sub arrays that ends at the index 3 all of these have an ending at the index 3 they're contiguous sub arrays and then here the sub problem here asks us if we have a sub array ending at 8 what is the best what is the maximum submarines sum we can achieve with the sub arrays ending at the index 8 so that is what this cell asks so each of these cells ask us what is the maximum contiguous sub array some we can achieve with sub arrays ending at each of these indices so the answer to the question for the whole array is going to be whichever these indices perform the best whichever of these indices have a sub array that ends at it that has the largest value the maximum contiguous submarine with the largest sub so that is what we're going to do and the key to understanding this is at each point in our iteration what does each item contribute what are the choices that we have at each element so we have two choices choice number one we can start a new sub array at a certain item we could start a new sub array at that item which means that the sub array at that item ends at itself if I have the subarray just just the for this arrey ends at index 3 so the answer at this cell of the best highest sum subarray ending at index 3 the answer could be 4 it could be 4 we might just take the 4 and that is our continuous summary that is the best we can do at this index that is choice number 1 we cut all our previous progress short and we say the best I can do ending here is myself that's choice number one choice number two is we can continue the maximum sub array coming before us with the item we are sitting at let's just pretend if we have a maximum sub array ending at the index 2 if the best we could do and to get index 2 is negative 12 when we are in next 3 does the 4 extend the previous bests we've done in terms of a maximum continue submarine or does 4 cut off the progress that we've had and just take itself so these are our two choices remember two choices do we start with this item for choice number one we chop off everything before us we just take the four our other choice we can continue the max sub array coming before us the best we could do in terms of maximum sub array some and to get in next to was negative 12 so the best we can do at 3 if we add on the item at index 3 is going to be this plus the item at 3 so negative 12 plus 4 so negative 12 plus 4 is negative 8 so which choice do we make do we choose negative 4 do we choose to start with this item sitting right here or do we choose to make this item an extension of the sub array Best's we've done before us so which would we choose we choose to have 4 start its own sub array so do you see how far is the winner here do you see that it is a better choice it's a better choice for us to choose to have 4 start its own sub array than for us to extend the sub array that was the best we could do right before us because we're going to be able to do better with just the four this is hard to grasp at first it takes time let it sink in but this is the essence of this problem and these are the two weighing choices we have okay so the way we can start this off is the best we can do ending at index 0 well it's just going to be index 0 on the code we have to have at least one item in our sub arrays so if we have a sub array and again in X 0 we have to include that item so the best we can do it in X 0 is going to be the item at index 0 itself okay and now we can start doing comparisons I'm sitting at index 1 the value of the item is 1 do I start a new contiguous sub array that ends at 1 and starts at 1 because it is the item itself or do I extend what came before me which do we choose let's compare our options so 1 if we start we could just take the value of the item or we do the best we've done right before us plus the item that we're about to use to extend so we get negative 2 plus 1 so which do I take do I take 1 or do I take negative 1 I'm going to take one the best sub array the max upper a sum of sub arrays ending at index 1 the best we can do is 1 and what did we do we only took the 1 we did not extend that would have heard us it would hurt us to extend this because our continuous sub array would have a sum of negative 1 it's better if we just take that item so now let's move on do we just take negative 3 do we start a new contiguous sub array and negative 3 that starts and ends at 2 or do I extend the best I could have done one index behind me the best I could have done is a amount of 1 so I could do 1 plus the value of this item to get the continuous sub array that would happen it could either be the whole thing we don't know what subarray was taken ending at 1 we don't know but we know that was one so we do one plus negative three what is the best we can do ending at index two it looks like the best we can do is negative two so we do that we just do negative two and what does this mean the best contiguous sub-array ending at index two looks like this it looks just like that do you see how we're extracting the best answer at every point and if we do this all throughout the array we're going to get a globally correct and optimal solution this is what dynamic programming is all about understanding our previous subproblems in work so we can understand the best answer to our current subproblem so we're sitting at index 3 so we have a value of 4 do I just start here or do I perform an extension on the best I could do one index behind me so negative 2 plus 4 which is better for or two Four Winds the best I can do and to get index 3 is starting at index 3 I just take the 4 the answer is 4 so let's move on so do we just take negative 1 when I say just take a negative 1 I mean do we just start a new sub array and negative 1 or do we extend the best we could have done before it 4 plus negative 1 is 3 do we take 3 or do we take negative 1 and decide to just start a negative 1 we want to take 3 we want to perform an extension I have no idea what the best subarray was ending at 3 but I know it's some was 4 and I know that negative 1 is albeit going to bring down the sum but it's still going to be better than starting a negative 1 so do we just take the 2 or do we perform an extension 3 the best we did before it plus the item 2 I'm going to take the 5 because 5 is bigger than 2 and now I am at this item do I just take the 1 and start a subarray all on my own or do I perform an extension 5 plus 1 is 6 do I perform an extension and have my best and ending at this end xb6 or do I just start at this index and it yields a 1 so I'm going to want to extend whatever the best was here I have no idea what it was but I'm going to take 6 so do I just take a negative 5 or do I do six plus negative five the best plus this item extending so the best of those is one I choose to perform an extension so do I just start at index eight and just take the four or am I going to extend the best one plus four and as you can see here what we're going to do is we're going to choose to perform an extension and we get five so this is the essence to this problem this is the essence to this algorithm this is how dynamic programming works we see the best answer between subproblems we see the previous work we've done previous best answers we've done and allows us to deduce the best answer to where we're sitting and we see that the best answer the best answer is right there it's going to be six and we can see that the sub array is going to look like this so this is the sub array with the best sub and notice how it ends at index six and the best we can do and the next six is the value of six so this is what this is about do not be worried if this does not make sense yet dynamic programming is very difficult it takes a lot of time for these things to sink in the idea of these subproblems relating to each other and it's not something that comes intuitively will come to you instantly it's not the most intuitive thing and in terms of time complexities and space complexity you can see we used linear space here and we ran in linear time but the code in the description shows you the constant space solution and runs in linear time as well so that is all for this video if you liked this video hit the like button subscribe to the channel this channel is all about empowering software engineers to excel in the interview and do their best and make these seemingly complex and difficult topics very simple to grasp so [Music]