1696

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        int score = nums[0];
        deque<pair<int, int>> dq;
        dq.push_back({nums[0], 0});

        // We just need to have max element in [i-k, i] index range,
        // this can be achieved using monotonic queue which is replacement for priority queue.
        for(int i=1; i<n; i++){
            // Pop indexes less than i-k.
            while(!dq.empty() && dq.front().second < i-k)
                dq.pop_front();
            score = dq.front().first + nums[i];

            // Have monotonically decreasing queue.
            while(!dq.empty() && score >= dq.back().first)
                dq.pop_back();
            dq.push_back({score, i});
        }
        return score;
    }
};