Jump Game VI
Medium · Stack & Strings · Array · Dynamic Programming · Queue · Heap (Priority Queue) · Monotonic Queue
Problem
You are given an integer array nums and an integer k. You start on index 0. In one move from index i you may jump forward to any index in [i + 1, min(n - 1, i + k)].
Your score is the sum of nums[j] over every index j you land on, including the first and the last. Return the largest score you can have when you reach index n - 1.
Examples
Input: nums = [2,-3,5,-8,1], k = 2 Output: 8
Land on indices 0, 2 and 4: 2 + 5 + 1 = 8. Each jump is 2 long, skipping both negatives.
Input: nums = [4,-1,-2,-3,6], k = 3 Output: 9
Index 4 is out of reach from 0, so one of the negatives must be visited; -1 costs least: 4 - 1 + 6 = 9.
Input: nums = [-5,2,-1], k = 1 Output: -4
With k = 1 every index is visited: -5 + 2 - 1 = -4.
Constraints
- 1 <= len(nums), k <= 10^5
- -10^4 <= nums[i] <= 10^4
Approaches
- Baseline: DP scanning the whole window — time O(n · k), space O(n)
Follow-up
A max-heap of (dp[j], j) also works: pop entries whose index is out of reach, then read the top. That is O(n log n), simpler to get right, and fast enough here; the deque is the linear version. To return the route itself, store for each index the j that gave its maximum and walk those links back from n - 1.
Related problems
Start free on Cariara · Coding problems · System design studio
