Leetcode 1814 Solution

This article provides solution to leetcode question 1814 (jump-game-vi)
Categories:
Tags:
Access this page by simply typing in "lcs 1814" in your browser address bar if you have bunnylol configured.

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

Solution

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

        s = deque([(dp, 0)])

        for i in range(1, len(nums)):
            dp = s[0][0] + nums[i]

            while s and i - s[0][1] >= k:
                s.popleft()

            while s and dp >= s[-1][0]:
                s.pop()

            s.append((dp, i))

        return dp