https://leetcode.com/problems/constrained-subsequence-sum

C++

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int K) {
        int ans=INT_MIN;
        vector<int> dp = nums;
        deque<pair<int, int>> dq;
        dq.push_back({nums[0], 0});
 
        for (int i=1; i<nums.size(); i++) {
            while(i-dq.front().second>K)
                dq.pop_front();
 
            dp[i]=max(dp[i], dq.front().first + nums[i]);
            while(!dq.empty() && dp[i] > dq.back().first)
                dq.pop_back();
 
            dq.push_back({dp[i], i});
        }
 
        for (int i=0; i<dp.size(); i++)
            ans=max(ans, dp[i]);
 
        return ans;
    }
};