Maximum Absolute Sum of Any Subarray - Leetcode 1749 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum absolute sum of any subarray so first thing before we even get into this problem I want to do you a small favor just in case you haven't solved the other problem before which is basically a very similar variation to this problem it's called Max subarray sum the main algorithm that's covered in that is a kadan's algorithm and so I have to be obligated to mention that this is a NE code 150 problem it is I guess falling into the greedy category but it could probably fall into some of the others as well I highly highly recommend solving this problem and learning the solution pretty well before tackling today's problem it is somewhat more difficult I would say today's problem that is if you want to learn kadan's a bit more in depth I think the advanced algorithms course covers it and then I kind of go through some additional algorithms that are related to a contain algorithm and I kind of compare and contrast them um but yeah anyways so in this problem we are given some numbers they could be positive and they could be negative so the input array that we're given this time is so we want to find the subarray such that we can take not the sum of that subay but the sum and then wrap the sum with like the absolute value so basically like long story short what we're looking for is like if I draw out like the number line here I think this is like the best way to visualize this if we're at zero in the middle we want to either be very far in this direction or very far in the other direction we either want to have like a very positive value because if you take the absolute value of that it's not going to change and if you have like a very negative value well that's just going to bring you like back around to the other side anyway so I'm not entirely sure how to visualize that but um basically what I'm saying is like this end and this end all we really care about is the distance from zero so that's what we care about for the entire some of that subray how far away is it from zero so that's kind of what makes this problem tricky because you kind of have to optimize for two different things at the same time I I guess this example doesn't do the best job of sort of illustrating this but uh maybe I start off with like a -2 and then another negative -2 and another negative2 so right now I'm going very negative like my sum here is -2 when I get to here it's ne4 when I get to here it's -6 and then maybe I start going in the other direction now I have have positive4 so actually I took my absolute value and I made it smaller now it's going to be uh -2 and then the absolute value of that of course is going to be positive two and I maybe just keep going in the other direction I keep getting positive values I do like a six now now my value is going to be positive4 and maybe I do another six and now I'm at 10 so sort of as we go through this and as we compute the sum maybe the subarray is starting at this value and we kind of keep doing that we see it's changing it's going in either direction so when we then try to actually find a solution for this problem one thing is pretty obvious The Brute Force solution should be pretty trivial to arrive at because we could just take every single subarray sum and just consider that and then find the one that leads to the absolute maximum and we know that there's going to be N squared different subarrays how do I know that there's N S Sub Rays because we'll have roughly n starting at this value so we'll have something like this and we'll have n starting at the next value technically not n but it's proportional to n so we'll have something like that and we'll kind of keep going I don't have enough space to show every single seay but we can see that the thing about this Brute Force approach what it's doing is pretty simple conceptually it's just taking it's considering every element what is the maximum absolute sum we could get starting at this value and now I want to show you how to optimize this and listen very carefully to the next couple minutes because if you can understand what I'm about to say you're actually very far ahead in terms of problem solving skills I promise you that we see this Brute Force solution we see how it's finding the optimal Solution by considering every subay starting at this element and going all the way through then every sub starting at this element going all the way through now can I tell you one of the problems with that approach because sometimes we can solve problems like this with like a two-pointer approach specifically like a sliding window type solution like isn't it possible that maybe we could find some kind of shortcut or some kind of repeated work and try to eliminate that and try to do so with like the two-pointer approach maybe when I get to some point like over here or I'm just arbitrarily picking these then based on some condition I realize okay now I need to start Shifting the left pointer because we've already found the maximum subarray sum starting here we know that there's never going to be a bigger one the problem with that approach is there's not a possible solution that works like that we can't solve this problem by trying to find the max subarray starting at a given element if we try to make that optimal we can't do that in a constant time because we don't know what's going to happen that goes back to what I was saying a couple of minutes ago when I said that as we go through this array the value could increase if we're trying to visualize that we could say that the sum starting at this value at some point maybe it's increasing at another point it starts decreasing then it goes up then it goes down we have no idea what the absolute Max or absolute Min is going to be and when I say absolute Min I'm specifically talking about like how far it can go in the negative Direction cuz ultimately those are the only points that we would care about so the solution to this problem is actually very simple and the reason I know it is because I've solved like these types of problems hundreds of times times so it just kind of automatically clicks for me to consider what I'm about to do but for you it might not so I would encourage you to try to whatever you're doing if it's not working just try considering inverting the way you're thinking about the problem think about it maybe in the opposite way and I'm going to do that and then I'm going to uh very easily solve this problem how about I consider the opposite how about for every element I ask myself what is the biggest subay sum or ending at this element not starting at the element but ending at the element all of a sudden the problem becomes very reasonable because first of all for the first uh subarray the one here now all of a sudden we don't have to iterate through everything else we know the maximum subray ending at this element without having to see the next elements it's pretty trivial for the first element you just take the absolute value of whatever it happens to be but as we continue through the array let me just pick some arbitrary element Maybe it's this one what am I going to do I mean I guess I could maintain a current sum I guess I could accumulate all the values I've seen so far perhaps when I get to this point it will be uh 1 + 5 - 3 that's going to be 3 so now when I say I want to find the largest sum ending at this element what are my choices like am I just going to take the entire thing or is it possible that actually removing some elements from the beginning which is the only thing we're allowed to do we need to have like a contiguous subarray so maybe we're allowed to remove one element maybe two maybe more whatever but we want to remove a prefix from this array so this is one of the reasons I think this is definitely a medium problem and if you're not familiar with some of the concepts I'm talking about this is definitely um a difficult problem not trying to make it sound like it's really easy so um but but the concept of a prefix isn't super crazy we have like uh this subarray just starting at the beginning or another one etc etc and by the way if you're not familiar with some of these Concepts you might want to consider checking out n cod. it's got a couple DSA courses that might be helpful but anyways we want to remove some prefix from here such that we can maximize what's left over which prefix would we be looking for keep that uh question in the back of your mind which one should we be removing right now let's just try kind of a Brute Force approach right now my sum is posi3 so you know maybe I remove this one or this one or this one or I can actually remove the entire thing we are allowed to take an empty subarray the sum of that of course would be zero so probably we'll never return a value less than zero makes sense uh we're also doing the absolute value of course um but now just kind of running through the boot Force I'm able to immediately recognize the pattern just by looking at this but I understand that if you haven't solved all these problems before it's not so obvious so let me walk you through it we could remove positive one that would bring us down to two we could remove uh -3 then which would then add three to this bringing us to postive 5 we could remove the positive2 as well bringing us back down to three or we could remove the last element bringing us back down to zero now the way I've kind of showed you this this is also an n s solution because we had to manually go through every single prefix to accomplish that but the good thing about this solution is we can do something clever given that we've seen all of these elements before we can try to notice the repeated work and that will ultimately lead you to the pattern to solve this problem which is very simply this if I was maintaining the prefix sums which I'll kind of draw down here they would look like this 1 and then I do the minus 3 bringing me down to -2 and then I add the positive2 bringing to zero and then I add the positive3 bringing me here I have this value let me draw it on like a really small graph in this corner over here let's say it's three it's like somewhere in the middle of this I want to either make this value go as high as it can go or as low as it can go so you tell me which one of these values should I remove from the current sum well it's kind of a trick question question that's kind of what makes this difficult there's two values that we actually have to try from this set now can you tell me which two values those are the maximum and the minimum is it all starting to make sense now well if it's not let me walk you through an example and by the way don't feel bad if it doesn't make sense like this is genuinely hard stuff especially when you're new to this so this is obviously the maximum in all of our prefix sums and this is obviously the minimum so let's try both let's take three and subtract two from it well that's going to add two to us and bring us up to five we could also try removing three that's going to bring us all the way back down to zero so among these two which resulted in the uh absolute maximum obviously this one did and so that's the value we would update our result with we're ultimately going to keep track of like what the maximum result happens to be okay but now you still might be thinking well how are you going to get the max and minimum from this array well we're not actually going to compute the prefix sums and store them in an array what we're going to do is keep track of the Max and the Min prefix sums at the same time we're going to maintain those just like we're maintaining the current sum so in summary let me do the dry run for you right now so we mainly keep track of these four variables the current sum the prefix Max the prefix minimum and the result of course we can probably just initialize these with zero and I think same for the these so then we will add one to this I'm going to be pretty rough with these notes but I think you'll probably understand most of it so then we have one we try removing these two and the way I'm going to do this is I'm actually not going to update these two variables until after we've already visited this by initializing our result to zero we're already accounting for the fact that we might end up with a zero so it does work out we try removing either of these it still leads to one so one is our maximum result up until this point here then we see this element as well we update our current sum it's going to be -2 and sorry I kind of messed up before we update this we would have also updated our prefix Max and prefix minimums prefix Min would have actually stayed the same because the previous uh sum that we had was one so one is not less than zero so that stays the same but the max will be increased to now one and we have our current sum now up until this point we try removing this from that that gives us -3 we try removing zero from that that gives us -2 you take the absolute value of each of these and you end up with three and two and which one of these is maximum it's three so then we can go ahead and update the result to now be positive 3 that makes sense because this is that maximum subarray that we've seen so far it's not this one and now we just keep going now we have the positive 2 we update our current sum to be zero now we can try removing this or actually sorry I keep messing up um before we update this we are now going to potentially update these two the prefix Max will be calculated like this with its existing value which is one and the current sum which is -2 which one of these is maximum it is definitely one we will do the same thing for prefix minimum but instead we will take the minimum of 0 and the -2 and we find that -2 is smaller so we can update this with -2 and then uh we will see the next element which is posit two we will update our current sum to be zero we will try to remove the maximum prefix which is one that's this that leaves us with this left over which is negative 1 that makes sense because if you take zero and subtract from it one then we end up with negative 1 the other thing would be to take 0 and subtract from it -2 that will actually give us 0 + 2 which will be two that makes sense if you look at the picture we would be removing this prefix and we would be left over with a two now that two is definitely not bigger than three so our result stays the same I'm getting kind of tired of doing this so I'm going to kind of fast forward through the rest uh but these two I don't think they will change we will see the next element it's positive three add that here now we have a a positive sum of three we could try subtracting three or we could try adding two by subtracting a negative number we end up adding two to this that gives us five five is bigger than the result go ahead and update this and we will end up updating the prefix maximum to B3 this stays the same we see the last element we end up with a current sum of uh -1 and by removing this from it 1 - 3 we end up with -4 take the absolute value of that that's going to be positive4 it's not bigger than this so our final result is going to be five and that is the correct return value and that by the way in this picture I think it would have just been this subarray so this is a linear time algorithm clearly we're not really doing anything fancy so now let's code it up so I'm going to start with the variables and I'm going to have the minimum prefix sum and the max prefix sum which are both initially going to be zero I'm going to have my current sum I'm just going to call it C and I'm going to have my result which I'm going to return Then simply I'm going to go through every number in nums we don't even need the index so it makes our life pretty easy we're always going to add this number to Cur then we want to calculate a couple things we want to calculate the current value minus the minimum prefix sum and then we want to take the absolute value of that we also want to try the absolute value of the current minus the max prefix sum and among these two we want to find the maximum and we want to use that maximum to potentially update our result now that line is going to get really long it is possible like I could do this in a python where I set this to be like the max of uh the result and whatever this happened to be but python actually makes things even easier because you can actually pass in like more than two values into this function so you can do something like this and that and lastly don't forget to update your minimum and maximum prefix sums I'm going to do that like this I set it to be the minimum of itself and the current sum and I'm going to just copy and paste this to do the opposite here where we're going to do the max prefix sum and the current and change this to Max so I know this probably looks really easy I'm glad that it does but that doesn't mean it's like trivial to come up with so always remember that but you can see here on the left it's pretty efficient both in terms of time and space I think it's constant space so if you found this helpful check out n code iio for more thanks for watching and I'll see you soon