leetcode- Jump Game VI

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int N = nums.size();
        for(int i = 1; i < N; i++){
            int cur_max = -1000000001;
            for(int j = i-k < 0? 0:i-k; j <= i-1; j++){
                cur_max = max(cur_max, nums[j]);
            }
            nums[i] = cur_max + nums[i];
        }
        
        return nums.back();
    }
};

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int N = nums.size();
        vector<int> dp(N);
        dp[0] = nums[0];
        deque<int> q;
        q.push_back(0);
        for(int i = 1; i < N; i++) {
            //	if q.front is outside of range of k, pop_front().
            //	maximum violation of range would be 1, therefore, 
            //	you don't use while. precise
            if(q.front() < i - k) q.pop_front();
            
			dp[i] = nums[i] + dp[q.front()];
            
            //	I am not sure why deleting from back.
            //	but if I deleted from front it won't work.
            while(!q.empty() && dp[q.back()] <= dp[i]){
                q.pop_back();
            }
            
            //	when the q was empty from avobe step,
            //	this will leave one element in the q
            q.push_back(i);
        }
        return dp.back();
    }
};