class Solution {
public:
int maxResult(vector<int>& nums, int k) {
deque<int> q;
int n = nums.size();
vector<int> f(n);
f[0] = nums[0];
q.push_back(0);
for (int i = 1; i < n; i ++ ) {
if (q.front() < i - k) q.pop_front();
f[i] = f[q.front()] + nums[i];
while (q.size() && f[q.back()] <= f[i])
q.pop_back();
q.push_back(i);
}
return f[n - 1];
}
};