Intuition
It is not hard at all!
If you read my previous article “Parallel Courses”, you may have already know when to use a greedy approach.
I think it is the time.
If you examine the previous K summed subsequences, you can easily select the largest one and add it to the value of the current Node N, or you may choose none of them. The choice made at the stage of N ensures that the result cannot change.
Since this approach is greedy, I won’t use dynamic programming and unnecessary memory space. Instead, we will use a queue. The queue is initialized with the first element, but I used a min-heap provided by the standard library and simply negated the sign.
By iterating through every element, the algorithm checks the largest sum found so far within k steps. If the biggest number is outdated, the while loop ensures it reaches its valid maximum. However, even though the sums are outdated, they must have been valid at some point, so we have to take them into account.
After all the steps are completed, we can consider the negated answer as the maximum we have sought for!
Code
import heapq
class Solution:
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
window = [(-nums[0], 0)]
ans = 10**8
for idx in range(1, len(nums)):
num = -nums[idx]
while window and window[0][1] + k < idx:
ans = min(ans, heapq.heappop(window)[0])
heapq.heappush(window, (min(num+window[0][0], num), idx))
return -min(ans, window[0][0])
Complexity
Time Complexity: O(N)
Space Complexity: O(K)
This iterates through the given numbers. Although this requires clearing the queue, the maximum number of elements going in and out of the queue is simply N. Therefore, it will be bounded by the linear graph. Since the maximum capacity of the queue is ‘K,’ we can confidently say that it is linear as well.