Jump Game 6

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 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.

Examples

Example 1:

Input: nums = [1,-1,-2,4,-7,3], k = 2
Output: 7
Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

Example 2:

Input: nums = [10,-5,-2,4,0,3], k = 3
Output: 17
Explanation: You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.

Example 3:

Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
Output: 0

Solution

Method 1 – Dynamic Programming with Monotonic Queue

Intuition

The key idea is to use dynamic programming to keep track of the maximum score to reach each index, and a monotonic queue (deque) to efficiently find the maximum score within the last k steps. This avoids recomputation and ensures optimal substructure.

Approach

Initialize a dp array where dp[i] is the maximum score to reach index i.
Use a deque to maintain indices of dp in decreasing order of their values, representing the best scores within the window of size k.
For each index i from 1 to n-1:

Remove indices from the front of the deque if they are out of the window [i-k, i-1].
Set dp[i] = nums[i] + dp[deque[0]] (the best score within the window).
Remove indices from the back of the deque if dp[i] is greater than or equal to their dp values (to maintain monotonicity).
Append i to the deque.

The answer is dp[n-1].

Code

C++

class Solution {
public:
   int maxResult(vector<int>& nums, int k) {
      int n = nums.size();
      vector<int> dp(n);
      dp[0] = nums[0];
      deque<int> dq;
      dq.push_back(0);
      for (int i = 1; i < n; ++i) {
        while (!dq.empty() && dq.front() < i - k) dq.pop_front();
        dp[i] = nums[i] + dp[dq.front()];
        while (!dq.empty() && dp[i] >= dp[dq.back()]) dq.pop_back();
        dq.push_back(i);
      }
      return dp[n - 1];
   }
};

Go

func maxResult(nums []int, k int) int {
   n := len(nums)
   dp := make([]int, n)
   dp[0] = nums[0]
   dq := []int{0}
   for i := 1; i < n; i++ {
      for len(dq) > 0 && dq[0] < i-k {
        dq = dq[1:]
      }
      dp[i] = nums[i] + dp[dq[0]]
      for len(dq) > 0 && dp[i] >= dp[dq[len(dq)-1]] {
        dq = dq[:len(dq)-1]
      }
      dq = append(dq, i)
   }
   return dp[n-1]
}

Java

class Solution {
   public int maxResult(int[] nums, int k) {
      int n = nums.length;
      int[] dp = new int[n];
      dp[0] = nums[0];
      Deque<Integer> dq = new ArrayDeque<>();
      dq.offer(0);
      for (int i = 1; i < n; i++) {
        while (!dq.isEmpty() && dq.peek() < i - k) dq.poll();
        dp[i] = nums[i] + dp[dq.peek()];
        while (!dq.isEmpty() && dp[i] >= dp[dq.peekLast()]) dq.pollLast();
        dq.offer(i);
      }
      return dp[n - 1];
   }
}

Kotlin

class Solution {
   fun maxResult(nums: IntArray, k: Int): Int {
      val n = nums.size
      val dp = IntArray(n)
      dp[0] = nums[0]
      val dq = ArrayDeque<Int>()
      dq.add(0)
      for (i in 1 until n) {
        while (dq.isNotEmpty() && dq.first() < i - k) dq.removeFirst()
        dp[i] = nums[i] + dp[dq.first()]
        while (dq.isNotEmpty() && dp[i] >= dp[dq.last()]) dq.removeLast()
        dq.add(i)
      }
      return dp[n - 1]
   }
}

Python

from collections import deque
from typing import List

class Solution:
   def maxResult(self, nums: List[int], k: int) -> int:
      n: int = len(nums)
      dp: List[int] = [0] * n
      dp[0] = nums[0]
      dq: deque[int] = deque([0])
      for i in range(1, n):
        while dq and dq[0] < i - k:
           dq.popleft()
        dp[i] = nums[i] + dp[dq[0]]
        while dq and dp[i] >= dp[dq[-1]]:
           dq.pop()
        dq.append(i)
      return dp[-1]

Rust

impl Solution {
   pub fn max_result(nums: Vec<i32>, k: i32) -> i32 {
      let n = nums.len();
      let mut dp = vec![0; n];
      dp[0] = nums[0];
      let mut dq: std::collections::VecDeque<usize> = std::collections::VecDeque::new();
      dq.push_back(0);
      for i in 1..n {
        while let Some(&front) = dq.front() {
           if front + k as usize < i {
              dq.pop_front();
           } else {
              break;
           }
        }
        dp[i] = nums[i] + dp[*dq.front().unwrap()];
        while let Some(&back) = dq.back() {
           if dp[i] >= dp[back] {
              dq.pop_back();
           } else {
              break;
           }
        }
        dq.push_back(i);
      }
      dp[n - 1]
   }
}

Complexity

Time: O(n) — Each index is pushed and popped from the deque at most once.
Space: O(n) — For the dp array and deque.