Here's the approach with the key 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: . Answer: the maximum over all , not just .
Space: for the DP array and deque.
Time: . Space: .