前言：看到这个题目的时候我们可以用大顶堆记录前面的最大值，这样我们转移的时候就少了很多繁琐的查询

---

题目地址

class Solution {
public:int constrainedSubsetSum(vector<int>& nums, int k) {int n = nums.size();vector<int> ans = nums;priority_queue<pair<int,int>> q;q.push({nums[0],0});for(int i=1;i<n;i++){while(q.top().second+k<i){q.pop();}int u = q.top().first;if(u>0){ans[i] += u;}q.push({ans[i],i});}int t = nums[0];for(int i=1;i<n;i++){t = max(t,ans[i]);}return t;}
};