Constrained Sum - Implementation

Here's the approach with this modification:

function constrainedSubsetSum(nums, k)
    n := length of nums
    dp := copy of nums
    deque := empty deque
    result := dp[0]
    deque.pushBack(0)
    for i from 1 to n-1
        // Remove indices outside window
        while deque not empty and deque.front() < i - k
            deque.popFront()
        // Add best previous if positive
        if deque not empty and dp[deque.front()] > 0
            dp[i] := nums[i] + dp[deque.front()]
        // Maintain decreasing order
        while deque not empty and dp[deque.back()] <= dp[i]
            deque.popBack()
        deque.pushBack(i)
        result := max(result, dp[i])
    return result

Time: $O(n)$. Answer: the maximum over all $dp[i]$, not just $dp[n-1]$.

Space: $O(n)$ for the DP array and deque.