Jump Game VI — Greedy + Monotonic Deque
Sanjeev SharmaAdvertisement
Problem
From each index, can jump 1..k steps forward. Score = sum of visited cells. Maximize.
Approach — DP + Monotonic Deque
dp[i] = max score reaching index i. dp[i] = nums[i] + max(dp[i-k..i-1]). Use monotonic deque to get window max in O(1).
Time: O(n) | Space: O(n)
Solutions
Python
from collections import deque
class Solution:
def maxResult(self, nums: list[int], k: int) -> int:
n=len(nums); dp=nums[:]
dq=deque([0])
for i in range(1,n):
while dq and dq[0]<i-k: dq.popleft()
dp[i]+=dp[dq[0]]
while dq and dp[dq[-1]]<=dp[i]: dq.pop()
dq.append(i)
return dp[-1]
Complexity
- Time: O(n) | Space: O(n)
Advertisement
