Kadane's Algorithm to Maximum Sum Subarray Problem

Key Takeaways

in this video I'm going to discuss the optimal solution to the maximum subarray problem which is called kadan's algorithm now let me explain what the maximum subarray problem is you might ask what's a subarray a subarray is basically an array within an array so an example of a subarray would be 21 in this example or just one element3 or it could be the whole array that's also a subarray but if we had -3 let's say and one that's not a subarray because a subarray needs to be contigous elements so a subarray is a set of contigous elements within the given array and the problem here is finding the subarray with the maximum sum here's what I mean if you look at this subarray 2 1 the sum is 2 + 1 = 3 and if we look at this subarray with -3 the sum is obviously just -3 and we are trying to find the one with the maximum sum in this example it's actually 21 with the S three and you can check it yourself too the simplest solution to this problem is the Brute Force solution basically checking all the possible subarrays and picking the one with the maximum sum so I would check the subarray starting at the first index and then check the ones starting at the second index and so on it's a good solution but it would take an order of n Square time and it's not the optimal solution the optimal solution to this problem is what's called Caden's algorithm I'm going to explain the idea behind it first and then we're going to go into the actual algorithm the idea is very simple we're going to look at each index and we're going to ask ourselves what's the maximum subray ending at this index so for the first index the maximum subray ending ending at this index is obviously just one and for the second index the maximum subarray ending at this index could be either 13 or just3 and the maximum one of those is 13 and for the 30 next we're going to do the same thing the maximum Subway or the subarray with the maximum sum ending at this index could be either two -32 or 132 and the maximum one of those is two if you compare the sums and we're going to do the same thing for each index for the rest of the indices and at the end we're going to compare those subarrays and we're going to find the maximum one of those in this case that's 2 one with the sum three as you can see the idea is very simple but it's not very efficient actually at least it's going to take an order of n Square time but the interesting idea from kadan's algorithm is that we can do much better than that actually we can run it under a linear time so let's see how we can do it let's say we using the same strategy here we're looking at each index and we are trying to find the maximum subray ending at that index and let's say we're looking at the third index and we know what the subarray uh from the pre previous index is and we're trying to find the maximum subray for this index or the maximum subray ending at this index so the interesting idea from kadan's algorithm is that that's um that maximum subray the local maximum subay is either this element the current element or the current element combined with the previous maximum Subway in this case that's 13 we can just compare these and ignore all the other subs and that's going to be the local maximum subay ending at this index so we're going to do the same thing for all the indices except for the first one because the first one we just pick the first element as the maximum subray and once we did that we're going to pick the maximum one of those and that's going to be the global maximum subarray and this algorithm is much faster than the Brute Force algorithm as I said it runs in a linear time now you might ask does it actually work if it does why does it work so let me explain that let's just say we're given this array and we're looking at the nth index we're running kadan's uh algorithm on it and now we at the N index and let's just say the element here is X and and we know what the subarray ending at the previous index is and let's call it m and the core idea from kadan's algorithm was that the maximum subarray ending at the N index is either just the current element X or the current element X combined with M so MX and as you can see M could be any number of elements and let me prove to you this is in fact the case to do that let's just assume that this is actually not the case that the maximum subarray ending at this element is neither X nor MX it's actually TX or something and I'm going to find a contradiction there so the t is either longer than M or it has more elements than m or it has less elements it doesn't matter either way but T is not empty because if it was empty it would be the same as just X and what I'm going to show now is that the sum of TX is and let's denote the sum with this symbol is less than the sum of MX this is actually less than or equal to but this is going to show that the TX is not the maximum subarray ending at the current index n the index or at least it's not the unique maximum subarray and it's very simple to show so the sum of TX is the sum of t plus X and the sum of MX is obviously the sum of M plus X and because we know that m is the maximum sum ending at the previous index it's at least larger than or equal to the sum of T which is also a subarray that ends at the previous index and this results shows that if you look at these equations the sum of TX is less than or equal to the sum of MX which in turn shows that the maximum Subway ending at the current index or the nth index needs to be either X the current element or the current element X combined with M which is the maximum subray ending at the previous index if we were trying to find multiple maximum subarrays the algorithm would be slightly different but the idea is the same now that we've explored how the algorithm Works let's just dive into the code here I'm just defining my function and the input is going to be the given array and the example I'm going to use here is this one and the output is going to be the sum of the maximum subarray and I'm not going to worry about where the maximum subarray is for now first of all I'm going to initialize all my variables to the first element in the array and the max current is the sum of the current maximum subarray or the maximum subarray that ends at the current index and Max Global keeps track of the global maximum sum and since the first element of the array is -2 I'm initializing both of them to -2 and I'm going to going to iterate the index I from one to the length minus one so that's going to be in this example from one to three the last index now let's look at the second index the or the index one this one what we are asking ourselves is what's the maximum subarray ending at this index is either three or -23 and the larger one is or the one with the larger sum is three so that's the maximum subarray ending at this index and the sum of that subarray is three so we're going to update C and that's larger than the global sum so we're going to update that as well in the code that's expressed as Max current is the maximum of or the larger of AI and Max current plus Ai and if the max current is larger than Max Global then update the max Global so let's do the same thing with the other indexes let's look at the third index two which is this one what we're going to ask ourselves here is what again what's the maximum subrate ending at this index it's either two or two combined with the previous maximum Subway 32 and obviously this is the one with the larger sum so we're going to pick this one we're going to update the current sum and we're going to update the current Global sum as well and we're just going to do the same thing for the last index and for the last index the current sum is going to be four and we're not going to update the global sum because that's larger than the current sum and at the end we're going to return this number the global sum and that corresponds to the maximum Subway in this example 32 all right that's it for the video and I hope you liked it if you want to watch more videos like this you can click right here to subscribe to my channel and see you soon