<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:
    struct TreeNode {
        int begin;
        int end;
        int val;
        TreeNode* left;
        TreeNode* right;

        TreeNode(int begin, int end, int val) : begin(begin), end(end), val(val) {};
    };

    TreeNode* build(vector<int>& arr, int begin, int end) {
        if (begin == end) {
            return new TreeNode(begin, end, arr[begin]);
        }

        int mid = begin + (end - begin) / 2;
        TreeNode* left = build(arr, begin, mid - 1);
        TreeNode* right = build(arr, mid, end);
        TreeNode* node = new TreeNode(begin, end, max(left->val, right->val));
        node->left = left;
        node->right = right;
        return node;
    }

    void update(TreeNode* root, int pos, int val) {
        if (root->begin == root->end) {
            root->val = val;
            return;
        }

        int mid = root->begin + (root->end - root->val) / 2;
        if (pos < mid) {
            update(root->left, pos, val);
        } else {
            update(root->right, pos, val);
        }

        root->val = max(root->left->val, root->right->val);
    }

    int find(TreeNode* root, int begin, int end) {
        int mid = root->begin + (root->end - root->val) / 2;
        if (end < mid) {
            return find(root->left, begin, end);
        } else if (begin >= mid) {
            return find(root->right, begin, end);
        } else {
            return max(find(root->left, begin, mid - 1), find(root->right, mid, end));
        }
    }


    int constrainedSubsetSum(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> pq;

        int res = INT_MIN;

        for (int i = 0; i < nums.size(); i++) {
            while (pq.size() && pq.top().second < i - k) {
                res = max(res, pq.top().first);
                pq.pop();
            }

            if (pq.size()) {
                pq.push({pq.top().first + nums[i], i});
            }

            pq.push({nums[i], i});
        }

        while (pq.size()) {
            res = max(res, pq.top().first);
            pq.pop();
        }

        return res;
    }
};
154212