Jump Game VI

Problem

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. Your score is the sum of all nums[j] for each index j you visited. Return the maximum score you can get.

Examples

The brute-force approach

DP: dp[i] = max score to reach index i. For each i, try all j in [i-k, i-1].

dp = [-inf] * n
dp[0] = nums[0]
for i in range(1, n):
    for j in range(max(0, i-k), i):
        dp[i] = max(dp[i], dp[j] + nums[i])
return dp[n-1]

O(n×k) — for each index, scan up to k previous indices.

Spotting the pattern

This is a Monotonic Queue problem. The key question to ask yourself:

What ordering does the deque maintain (front to back)? How does that guarantee the front always gives the maximum dp value in the window?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.