Constrained Subsequence Sum - Leetcode 1425 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem constrained subsequence sum we're given an integer array of nums and an integer K we want to return the maximum sum of a non-empty subsequence but there is a bit of a restriction here so take a look at this array and in this example K is equal to two so what that means is we want a subsequence and typically with subsequence is we can say okay we can include this element or we can skip this element and we can do that for every single element so we might end up like let's say choosing this and we could skip an arbitrary number of elements we could have a gap that is arbitrarily large but in this problem our Gap is actually limited by K so it's a little bit unintuitive so if K is two that doesn't mean that the max Gap can be equal to two it means that the maximum distance between elements that we include can be two so if K is equal to two we can skip at most one consecutive element so typically with subsequence problems it's pretty common to solve these with dynamic programming and that's definitely the case with this problem it's possible to solve it with dynamic programming and I'll actually show you the dynamic programming solution but you're going to notice we do get time limit exceeded and the hint that you would get time limit exceeded is that the dynamic programming solution for this problem is actually very very easy it's pretty common with subsequence problems like for example in the longest increasing subsequence problem and I would recommend checking that problem out if you struggle with this one it's somewhat similar not like exactly the same but the idea is that for every position the sub problem is what would be the result of this problem like what would be the maximum sum that we can get with this array aray and what would be the maximum that we can get with this subarray and this subarray and this subarray etc etc so these are kind of our sub problems but it's actually not just that simple there's one more catch to the sub problem for example for this sub problem we're not just Computing the maximum sum but we're specifically Computing the maximum sum that includes the last element in this subarray and we're doing that very very deliberately with the longest increasing subsequence problem we do that because we want to know like if we're Computing this sub problem we want to ensure that the elements that we're including are in increasing order and we want the last element of like the previous sub problem and we want to be able to ensure that these are in increasing order that's for the Lis problem but for this problem it's a little bit different why do you think we would want to know that for sure this element exists in the subsequence for example by the time we get here by the time we're trying to compute the sub problem for this value and this subarray why would we want to know what the solution would be for this sub problem this sub problem and this sub problem where all of those actually include the last integer because we want to know and I'm actually just going to start uh Computing it really quickly we're going to call it DP what would be the Maxum ending here where we must include this element it would be 10 what would be the max ending here where we include uh this element it would be 12 because we're definitely including this and we have a choice whether we want to include this or not so we of course are going to now when we get here we have a -10 we have to include the -10 and now we have a choice to make actually we can look at the two previous values in the DP array the reason we can look at these two is because we know if if we look at this value 12 we know for sure we included this value so the Gap would be sufficiently small and if we look at the 10 we know for sure we included this and this Gap is also sufficiently small so what we do with these two values is compare them which one is greater 12 so we're going to take 12 and add it to -10 we're going to get a two over here so this is basically how we solve the problem for the five we're going to do the same thing we have to include the five but which one of these two are we going to include probably the 12 so then we get 17 over here and then lastly we get 20 we have to include it we look at the two previous values and we don't by the way have to include these two because if we chose I'm going to skip this and I'm going to skip this that would mean we skipped everything except we included the 20 and that's perfectly valid because it guarantees that our subsequence is nonempty and it also ensures that the Gap is small because yes we can have one ele element and we can start anywhere in the array like this does not count as a gap because the Gap only exists between two elements that we've actually chosen so here with this 20 we choose the maximum of these two if they were both negative that would be the case where we don't include either of them but they're not negative so we include the 17 we get a 37 in the last spot and then for all of these we're just going to take the maximum of them and then return that and we got 37 and that is the solution to this problem now the only downside with this solution like I said like this is the solution this works to solve this problem but it's almost too easy and that's why it gets time limit exceeded the overall time complexity here is going to be big of n where n is the size of the input array but notice for every element we might have to look at the K previous values in our DP array so the time complexity becomes big of n * k space complexity for for the DP array is going to be Big O of n though we could optimize it to Big O of K if we really wanted to because you notice that we only need the K previous elements in the array but I'm not even going to make that optimization because this won't pass anyway I just want to quickly show it to you so I'm going to create that DP array that I was talking about we're going to initialize it with all zeros for now but the length is going to be the length of the input array nums and we already know that the first value is is pretty straightforward it's just going to be the first value in the array so I'm just going to initialize that and then when I start my Loop I'm going to start at index one rather than index zero and at this point it becomes pretty straightforward we're going to just have a loop I'm going to use index J we're going to go over the K previous values which would be from I minus K all the way up until but not necessarily including I and this might end up end up being negative so if we want to we can say Max of 0 and IUS K so that we don't ever get anything less than zero and uh at this point it's pretty much Computing the maximum so for DP of I we want to compute what's the max possible sum that we can get here and we do that by either uh setting it to itself or setting it to the current number plus DP of J we're looking at the K previous uh sub problem results and considering adding them to the current number now there's one last catch notice that this actually doesn't include the possibility that we might just want DP of I to be nums of I itself meaning we don't include any previous sub problems so to handle that case I'm going to initialize DP of I with nums of I and if we wanted to actually uh get rid of this we could instead initialize our DP array like this n for n in nums and that will pretty much do the same thing I think this is slightly less readable but uh you can kind of choose what you'd like but at this point we've solved the problem at this point we just have to return Max of DP now you can see though after running the code we do get time limit exceeded on one of the large inputs and that's because if we look at the left we find that K can potentially be the same size as the length of the input array so K might not be very small and you can see in this example K is very very big that means our solution is not super efficient let's try to optimize it so this solution the one that we coated up is actually not too far away from a more optimized solution it's kind of reminiscent of like the sliding window solution like we want to keep a window of Max size K as we iterate so like at this point we' we might want like a window of the K previous elements and that's kind of what we're doing with these values but even if we do that like even if we implement the sliding window for us to go through the values in that window and find the maximum of them that's the inefficient part that's the part that is taking us Big O of K time can we do that any more effici well possibly with a heap like if these values are within a heap probably a Max Heap more specifically we can then theoretically pop it in log K time so how can we try to use a heap to more efficiently solve the problem because at first to be honest it seems like a heap won't work and let me tell you why initially you might think it's not going to work because let's say we get to this point like let's say we're at five and we have these two elements in our Heap 12 and two we want to get the maximum of them that's pretty easy to do we just get 12 right that's going to be the maximum that's kind of what the max Heap is for so we do that very efficiently we do that very easily now it's time for us to shift to the right we're at 20 and maybe when we were at five we also included this 17 adding to a heap is pretty easy okay now it's our turn to remove from the Heap just like the sliding window right we want to remove this leftmost element just like it's a sliding window problem well that's not what a heap is for remember when we remove from heaps we can remove the max element and in this case it actually looks like it works when we remove the max we remove the leftmost element okay but now when we try to do it again now when we're at 20 okay we include let's say this the 37 and now we're trying to pop this leftmost element from the Heap well since this is a Max Heap it's going to end up popping the 37 but what we actually want to do is pop based on the index and we can't do that for us to remove by an index if the max Heap is sorted by these values we can't do that that's going to be inefficient but my proposal to you and this is kind of the hard part of this problem this is why it's a hard that it actually is possible for us to solve this problem and we don't necessarily have to remove the leftmost element and let me show you why let me kind of dry run through this I'm going to leave these values here so that we don't have to recompute them but assume that that's kind of what we're doing that's what we're doing to solve this problem right now so we start at 10 we already know that the max result for that is going to be 10 okay then we get to two and this is now a part of our Max Heap when we add this to the Heap not only do we add 10 but we add the index zero that this ended at so keep that in mind we're also adding the index for all of these into our Max Heap now when we're at two we can take that 10 and add it to two and then we're going to get 12 here so now we'll have another one in our Heap we'll have 12 and one and we don't have to remove yet because the Gap is not large enough we have k equals 2 we have not exceeded that in our Heap so then we get to -10 over here and once again we're going to get the max from our Heap and we don't have to pop from the he to get the max we get 12 12 + -10 is going to be 2 so now we add two to the max Heap so we have two and index two is the second value but now when it comes for five for us to compute the value that goes here we cannot consider all three of these but that actually doesn't necessarily mean that we have to remove the 10 immediately because what we're going to do is only consider of all of these we're going to first find what's the max value right now it happens to be 12 okay and we're going to try to add 12 and five together but before we can do that we have to ensure that the index that this 12 was ending at the differential between that index and the index that we're currently at is less than or equal to two and right now that does happen to be the case so there's nothing for us to do there's no no problem here just because we have multiple values in the Heap doesn't mean we're necessarily using the ones that are out of bounds and if we were using the ones that are out of bounds we would try to pop that first so right now we're able to do things we're able to compute the 17 and add it to the Heap now the values in our Heap are going to be 17 and the index was three now by the time we get to 20 we're kind of going to do the exact same thing we're going to try to get the max from the Heap it's going to be 17 we're going to find that the index was three the index here is four so the differential is small enough and then we're going to end up Computing the 37 but what if it wasn't like what if hypothetically this was a seven and we instead got these two values from the max Heap well we're trying to compute 20 plus whatever the max we can get from the max Heap is we find that it's 12 initially now this differential is definitely too large 12 was at index one we're currently I think at index 4 so this differential is too large what are we going to do this would not be valid 12 + 20 would not be valid so what we actually do is pop this guy from our Heap it's kind of a greedy algorithm at this point now we try the same thing again we try to get the max from the Heap we find that it's 10 once again this Gap is too large so we pop 10 from the Heap as well so these two are out of the Heap and then we'd only be left with uh these two values and then we would find that this one is the next largest and it happens to be close enough so we would take that and add it here so that's kind of the intuition of solving this with a Max Heap now you might notice that the downside is that the Heap is not necessarily going to be limited to a size of K it could actually be as long as the input array itself so the overall time complexity is going to be n because we're iterating over the array and we might end up pushing and popping every single value to the Heap so that's going to be log n and that's the overall time complexity for this solution and a memory complexity is also bigger of n because that could be the max size of our Heap so now let's code up this more optimized solution okay so now let's code this up and one thing I didn't mention previously is that we actually don't need to compute the entire DP array because remember remember we're just using the Heap to have those elements anyway so that's uh why I'm just going to maintain a single variable for the result and we're going to initialize it kind of the same way it's going to be the first value since once again we're going to have our Loop for I in range starting at index one we're going to initialize the Heap similarly to the way we did the DP array previously we're just going to have the max Heap initialized with the first value nums at index zero and the second value in this pair is going to be the index which is a zero so I'll make a quick comment here so this is going to be the first value is going to be the max sum and it's going to be ending at this particular index and one thing to mention though is python actually doesn't have Max heaps this is going to be a Min Heap by default and for us to get around that we can just make the key in this case be negative so we're going to be pushing and popping based on what this value happens to be and we'll have to keep in mind that we've made it negative so if we want the original value we'll have to add another negative after we pop it okay now what we would normally do is compute the current sum the current Max sum and ending at index I kind of the same way that we did before we're going to take the max of the number itself at this index or the number itself added with the value that we get from the max Heap which we would get like this Max Heap at index zero that's going to give us the top of the Heap and of the top of the Heap we want the first value which was the actual Max sum so once again we say index zero and remember we made this negative so if we want the True Value here we have to add another negative sign so instead of making this a plus I'm going to make it a negative so what this is doing is it's saying we're taking the current value plus the max sum that we could have possibly computed anywhere in the max Heap and adding them together and we might not even use this value in our result like we also consider this possibility as well but you might see the problem here we don't necessarily want to pop anything from the max Heap we only want to get the value if the index is within the range of K so before we even do this we have to ensure that the index actually is in range how do we do that well we have to make sure that I the current index minus the index at the top of the Heat which is at index zero and for us to get the index this time which is the second value in that pair we do one so this is the top of the Heap this is what we would be adding here but we only want to do this if it's in Balance if this is less than or actually in this case if this is a greater than K because we know this is always going to be positive because I is always going to be greater than the previous indices so if this is the case what we want to do is say Heap Q Heap pop from the max Heap and we can't just make this an if statement you might be thinking with like a typical sliding window we probably only are going to shift by one as we iterate through the input array but remember for reasons I talked about earlier because the Heap could be arbitrarily large we actually need this to be a while loop so this way after the while loop is done we know for sure that the top of the Heap will be close enough to the current index and we also actually guarantee that the Heap won't be empty either because for any index I I minus one will be within the Heap the index I minus one the previous index will be in the Heap and that's always going to be considered valid and that's because K is always going to be greater than or equal to one so that's why we can kind of get away with that now after you've done this you've more or less solved the problem so at this point we would want to maximize our result so the result might be itself or it might be the current Max that we ended up Computing and lastly before we go to the next iteration of the loop let's also push this to our Heap so we're going to say Heap q. Heap push to the max Heap this pair of values which is the current Max but remember every time we add it to the Heap we kind of have to make it negative because uh we're simulating this using like a minimum Heap under the hood and the second is going to be of course the index of this current maximum that we're currently at so that's the solution all we have to do now is return the result that's the entire code let's run it to make sure that it works as you can see on the left yes it does and it's relatively efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon