1696. Jump Game VI

You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.

You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.

Return the maximum score you can get.

• new solution update 2022.07.09

class Solution {
public:
    int maxResult(vector<int>& A, int k) {
        priority_queue<pair<int,int>> pq;
        pq.push({A[0],0});
        int res = A[0];
        for(int i = 1; i < A.size(); i++) {
            while(!pq.empty() and pq.top().second + k < i) pq.pop();
            res = pq.top().first + A[i];
            pq.push({res, i});
        }
        return res;
    }
};

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int sz = nums.size();
        vector<long> v(sz, INT_MIN);
        v[sz - 1] = nums[sz - 1];
        queue<pair<int, long>> q;
        q.push({sz - 1, v[sz - 1]});
        while(!q.empty()) {
            auto p = q.front();
            q.pop();
            if(p.second < v[p.first])
                continue;
            pair<int, int> small{sz, INT_MIN}, far{sz, INT_MIN};
            bool flag = true;
            for(int i = p.first - 1; i >= max(0, p.first - k); i--) {
                if(nums[i] >= 0 && v[p.first] + nums[i] > v[i]) {
                    v[i] = v[p.first] + nums[i];
                    q.push({i, v[i]});
                    flag = false;
                    break;
                }
                if(nums[i] < 0 && v[p.first] + nums[i] > v[i]) {
                    if(small.first == 0) {
                        small.first = i;
                        small.second = v[p.first] + nums[i];
                    } else {
                        if(small.second <= v[p.first] + nums[i]) {
                            small.first = i;
                            small.second = v[p.first] + nums[i];
                        }
                    }

                    far.first = i;
                    far.second = v[p.first] + nums[i];
                }
            }
            if(flag && small.first != sz) {
                q.push(small);
                v[small.first] = small.second;
                if(far.first != small.first) {
                    q.push(far);
                    v[far.first] = far.second;
                }
            }
        }

        return v.front();
    }
};