【題解】LeetCode 1425. Constrained Subset Sum Hard

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int sz = nums.size();
        long long dp, ans = -10005;
        deque <pair<long long, int> > dq;
        dq.push_back({0, -1});
        for (int i = 0; i < sz; i++){
            while (!dq.empty() && dq.front().second < i-k) dq.pop_front();
            if (!dq.empty()) dp = nums[i] + max(0LL, dq.front().first);
            else dp = nums[i];
            while (!dq.empty() && dq.back().first <= dp) dq.pop_back();
            dq.push_back({dp, i});
            ans = max(ans, dp);
        }
        return ans;
    }
};