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

<p>A <em>subsequence</em> 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.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,2,-10,5,20], k = 2
<strong>Output:</strong> 37
<b>Explanation:</b> The subsequence is [10, 2, 5, 20].
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,-2,-10,-5,20], k = 2
<strong>Output:</strong> 23
<b>Explanation:</b> The subsequence is [10, -2, -5, 20].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public: 
    int tree[4*100001] ; 
    void update(int node, int low, int high,int val, int ind) {
        if(low==high) {
            tree[node]=val; 
            return ; 
        }
        int mid=(low+high)>>1; 
        if(ind<=mid) {
            update(2*node,low,mid, val, ind)  ; 
        }
        else {
            update(2*node+1,mid+1, high, val , ind) ; 
        }
        tree[node]=max(tree[2*node],tree[2*node+1]) ; 
    }
    int rangequery(int node, int low, int high, int l, int r) {
           if(l>high or r<low) {
               return 0; 
           }
           if(low>=l and high<=r) {
               return tree[node] ; 
           }
           int mid=(low+high)>>1; 
           int left=rangequery(2*node, low, mid, l , r) ; 
           int right=rangequery(2*node+1, mid+1, high, l, r) ; 
           return max(left, right) ; 
    }
    int constrainedSubsetSum(vector<int>& nums, int k) {
         int n=nums.size() ; ; 
         vector<int>dp(n,-1e9) ;
         dp[0]=nums[0] ; 
         update(1,0,n-1,dp[0],0) ; 
         for(int i=1; i<n; i++) {
                int left=i-k; 
                if(left<0) left=0; 
               int  prev=rangequery(1,0,n-1,left,i-1) ; 
               if(prev>=0) dp[i]=prev+nums[i]; 
               else dp[i]=nums[i] ;  
               update(1,0,n-1,dp[i],i) ; 
         }
         int res=dp[0] ; 
         for(int i=1; i<n; i++) res=max(res , dp[i]) ; 
         return res;  
    }
};
123662