Constrained Sum - DP Formulation

Let $dp[i]$ be the maximum sum of a subsequence ending at index $i$.

Transition: $dp[i] = nums[i] + \max(0, \max_{j \in [i-k, i-1]} dp[j])$ You either start fresh at $i$ (just $nums[i]$) or extend from some $dp[j]$ within distance $k$.

Naive implementation: $O(nk)$ because you scan $k$ previous states. With monotonic deque: $O(n)$ by maintaining max over the sliding window of $dp$ values.