1696.Jump Game 6

'''
You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.

You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.

Return the maximum score you can get.
'''
#method 1 Monotoic Queue
Keep queue such that elements are in decreasing order
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        q=deque()
        n=len(nums)
        q.append(n-1)
        dp=[0]*n
        dp[-1]=nums[-1]

        ans=0
        for i in range(n-2,-1,-1):
            if q[0]-i>k:
                q.popleft()
            dp[i]=dp[q[0]]+nums[i]
            while q and dp[q[-1]]<dp[i]:
                q.pop()
            q.append(i)
        return dp[0]
#method 2 Using heap
import heapq as hq
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        h=[]
        ans=None
        n=len(nums)
        for i in range(n-1,-1,-1):
            while h and h[0][1]-i>k:
                hq.heappop(h)
            item=(-(-(h[0][0] if h else 0)+nums[i]),i)
            hq.heappush(h,item)
            ans=-item[0]
        return ans