#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/monotonic-queue-optimization/jump-game-vi-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/monotonic-queue-optimization/jump-game-vi-implementation

Repovive

LeetCode 1696 Jump Game VI - Implementation - Monotonic Queue Optimization | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 1696 Jump Game VI - Implementation

The code

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.

Time: $O(n)$ . Space: $O(k)$ .