Constrained Sum - Implementation

Here's the solution:

function constrainedSubsetSum(nums, k)
    n := length of nums
    dp := copy of nums
    deque := empty deque // stores indices

    for i from 0 to n - 1
        // Get max from valid range
        if deque is not empty
            dp[i] := max(dp[i], dp[i] + dp[front of deque])

        // Maintain decreasing order by dp value
        while deque is not empty and dp[i] >= dp[back of deque]
            pop back from deque

        push i to back of deque

        // Remove out-of-range indices
        if front of deque <= i - k
            pop front from deque

    return max element in dp

Time: $O(n)$. Space: $O(n)$.