Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i &lt; j, the condition j - i &lt;= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

&nbsp;
Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].


Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.


Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].


&nbsp;
Constraints:


	1 &lt;= k &lt;= nums.length &lt;= 105
	-104 &lt;= nums[i] &lt;= 104


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        deque = []
        for i, num in enumerate(nums):
                
            while(deque and deque[0] < i - k): # delete that didn't end with a number in A[i-k:i]
                deque.pop(0)
                
            if deque:  # compute the max sum we can get at index i
                nums[i] = nums[deque[0]] + num
            
            while(deque and nums[deque[-1]] < nums[i]): 
                # delet all the sequence that smaller than current sum, becaus there will never be
                # considers ==> smaller than current sequence, and end before current sequence
                deque.pop()
                
            if nums[i] > 0: # if nums[i] < 0, it can't be a useful prefix sum    
            	deque.append(i)
        
        return max(nums)
class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n=nums.length;
        int[] dp=new int[n];
        int res=nums[0];
        Queue<Integer> queue=new PriorityQueue<>((a,b)->dp[b]-dp[a]); //Declaring Max heap

        Arrays.fill(dp,Integer.MIN_VALUE);
        dp[0]=nums[0];
        queue.offer(0);

        for(int j=1;j<n;j++){
            int i=Math.max(j-k,0); // get the furthest index possible
            while(!queue.isEmpty() && queue.peek()<i) queue.poll(); // find the global max in the specified range for that particular j index
            int idx=queue.peek();
            dp[j]=Math.max(dp[idx]+nums[j],nums[j]);
            res=Math.max(res,dp[j]);
            queue.offer(j);
        }
        return res;
    }
}
class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        priority_queue<array<int, 2>> que;
        int ret = nums[0], curr;
        que.push({nums[0], 0});
        for (int i = 1; i < nums.size(); i++) {
            while (!que.empty() && que.top()[1] < i - k) {
                que.pop();
            }
            curr = max(0, que.top()[0]) + nums[i];
            ret = max(ret, curr);
            que.push({curr, i});
        }
        return ret;
    }
};
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var constrainedSubsetSum = function(nums, k) {
    const queue = [[0, nums[0]]];
    let max = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const cur = queue.length ? nums[i] + Math.max(0, queue[0][1]) : nums[i];
        max = Math.max(max, cur);
        while(queue.length && queue[queue.length-1][1] < cur) queue.pop();
        queue.push([i, cur]);
        while(queue.length && queue[0][0] <= i-k) queue.shift();
    }
    return max;
};
Constrained Subsequence Sum