1696. Jump Game VI

https://leetcode.com/problems/jump-game-vi/

Python

from collections import deque


class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        dp = [0]*len(nums)
        dp[0] = nums[0]

        queue = deque([0])

        for i in range(1, len(nums)):
            while queue and queue[0] < i-k:
                queue.popleft()

            dp[i] = dp[queue[0]] + nums[i]
            while queue and dp[i] > dp[queue[-1]]:
                queue.pop()

            queue.append(i)

        return dp[-1]