b_lc_跳跃游戏 VI（单调队列dp）

开始你在下标 0 处。每一步，你最多可以往前跳 k 步。你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。

思路：单调队列维护当前位置前面最大k个位置的最大得分的下标（可O(1)取出）

const int N=1e5+5;
class Solution {
public:
    int n,f[N];
    int maxResult(vector<int>& A, int k) {
        n=A.size();
        for (int i=0; i<n; i++) f[i]=A[i];
        deque<int> q; q.push_back(0);

        for (int i=1; i<n; i++) {
            while (!q.empty() && q.front()<i-k) q.pop_front();
            f[i]=f[q.front()]+A[i];
            while (!q.empty() && f[q.back()]<f[i]) q.pop_back();
            q.push_back(i); 
        }
        return f[n-1];
    }
};