力扣1425.带限制的子序列和

• 单调队列优化dp

  • f[i] 表示在数组的前 i 个数中进行选择，并且恰好选择了第 i 个数，可以得到的最大和
  • 状态转移：f[i] = max(max(f[j]) , 0) + nums[i];
  • 单调队列优化：储存前K个f[i]，并且单调，便于找到最大的f[j]
    • 更新逻辑：当i > j时，如果f[i] >= f[j]，说明f[i]更优

•   class Solution {public:int constrainedSubsetSum(vector<int>& nums, int k) {int n = nums.size();vector<int> f(n);//初始化f[0] = nums[0];deque<int> q;q.push_back(0);int ans = nums[0];for(int i=1;i<n;i++){//弹出出界元素while(!q.empty() && i - q.front() > k)q.pop_front();//更新f[i]f[i] = max(f[q.front()],0) + nums[i];ans = max(ans,f[i]);//更新单调队列while(!q.empty() && f[i] >= f[q.back()])q.pop_back();q.push_back(i);}return ans;}};