力扣1425.带限制的子序列和
力扣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; } };