LeetCode 1696 Jump Game VI - Implementation

Here's the faster approach:

function maxResult(nums, k)
    n := length of nums
    dp := array of size n
    dp[0] := nums[0]
    deque := empty deque
    deque.pushBack(0)
    for i from 1 to n-1
        // Remove indices outside window
        while deque not empty and deque.front() < i - k
            deque.popFront()
        // dp[i] = best previous + current value
        dp[i] := dp[deque.front()] + nums[i]
        // Maintain decreasing order
        while deque not empty and dp[deque.back()] <= dp[i]
            deque.popBack()
        deque.pushBack(i)
    return dp[n-1]

Time: $O(n)$. Space: $O(n)$ for DP array, $O(k)$ for deque. This is the template for monotonic queue DP improvement.