# Jump Game VI
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/jump-game-vi)
Canonical: https://scaleengineer.com/dsa/problems/jump-game-vi
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Heap (Priority Queue), Queue, Monotonic Queue
**Companies:** [AQR Capital Management](https://scaleengineer.com/companies/aqr-capital-management)
---
## 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_.

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

**Constraints:**

* `1 <= nums.length, k <= 105`
* `-104 <= nums[i] <= 104`

# Approaches
## Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define `dp[i]` as the maximum score achievable to reach index `i`. To compute `dp[i]`, we need to find the maximum score among all possible previous indices `j` from which we can jump to `i`. These indices `j` are in the range `[i - k, i - 1]`. The recurrence relation is `dp[i] = nums[i] + max(dp[j])` for `j` in `[max(0, i - k), i - 1]`. We build up the `dp` array from the beginning to the end.
**Time:** O(N * K), where N is the number of elements in `nums`. For each element `i`, we look back at `k` previous elements. · **Space:** O(N) to store the `dp` array.
**Pros:** Simple to understand and implement.; It correctly formulates the problem as a dynamic programming recurrence.
**Cons:** The time complexity of O(N * K) is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We can solve this problem using dynamic programming. Let's define `dp[i]` as the maximum score to reach index `i`. Our goal is to find `dp[n-1]`.

**Base Case:**
The base case is `dp[0] = nums[0]`, because we start at index 0 and its score is included.

**Recurrence Relation:**
For any index `i > 0`, we can reach it from any index `j` such that `i - k <= j < i`. To maximize the score at `i`, we must have come from the previous index `j` that had the maximum score. Therefore, the score at `i` is `nums[i]` plus the maximum score in the window `dp[i-k...i-1]`.

`dp[i] = nums[i] + max(dp[i-1], dp[i-2], ..., dp[i-k])`

We can implement this by iterating from `i = 1` to `n-1` and, for each `i`, iterating again through the last `k` indices to find the maximum `dp` value.

```java
class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];

        for (int i = 1; i < n; i++) {
            int maxPrev = Integer.MIN_VALUE;
            for (int j = 1; j <= k && i - j >= 0; j++) {
                maxPrev = Math.max(maxPrev, dp[i - j]);
            }
            dp[i] = nums[i] + maxPrev;
        }
        return dp[n - 1];
    }
}
```
### Algorithm
*   Create a DP array `dp` of size `n`, where `n` is the length of `nums`.
*   Initialize `dp[0] = nums[0]`, as the score to reach the first index is just its value.
*   Iterate with a loop from `i = 1` to `n - 1`.
*   Inside this loop, create another loop to find the maximum score among the previous `k` reachable indices. Let this be `max_prev`. The inner loop iterates from `j = 1` to `k` (as long as `i - j` is a valid index).
*   Update `dp[i] = nums[i] + max_prev`.
*   After the outer loop finishes, `dp[n - 1]` will hold the maximum score to reach the last index.

## DP with Max Heap
The bottleneck in the basic DP approach is the repeated search for the maximum value in a sliding window. This can be optimized. Instead of a linear scan, we can use a data structure that provides the maximum element more efficiently. A max heap (or a priority queue) is a suitable choice. We can maintain a max heap of the scores of the last `k` indices. For each step `i`, we find the maximum score in the window `[i-k, i-1]` by looking at the top of the heap, after removing outdated entries.
**Time:** O(N log K). Each of the N elements is pushed and popped from the heap at most once. Heap operations take O(log K) time, as the heap size is bounded by `k`. · **Space:** O(K) to store at most `k` elements in the priority queue.
**Pros:** Much more efficient than the naive DP approach, and it's fast enough to pass the given constraints.; The logic is a standard optimization for sliding window problems.
**Cons:** Slightly more complex to implement due to the use of a Priority Queue.; The logarithmic factor in the time complexity makes it less efficient than the optimal O(N) solution.
### Explanation
To improve upon the O(N*K) complexity, we need a faster way to find the maximum in the sliding window `dp[i-k...i-1]`. A max heap can find the maximum element in O(1) time (peeking) and supports insertions in O(log K) time. The heap will store pairs of `(score, index)`.

As we iterate from `i = 1` to `n-1`:
1.  We first prune the heap by removing all elements `(score, j)` where `j` is no longer in the current window (i.e., `j < i - k`).
2.  The top of the heap now gives us the maximum score from a valid preceding index. Let this be `max_prev_score`.
3.  We calculate the score for the current index `i` as `current_score = nums[i] + max_prev_score`.
4.  We then add `(current_score, i)` to the heap.

This process ensures that for each `i`, we can find the required maximum in O(log K) time on average, leading to a much better overall time complexity.

```java
import java.util.PriorityQueue;

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        // PriorityQueue stores pairs of [score, index]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        
        int maxScore = nums[0];
        pq.offer(new int[]{nums[0], 0});

        for (int i = 1; i < n; i++) {
            // Remove elements from the heap that are outside the window of size k
            while (pq.peek()[1] < i - k) {
                pq.poll();
            }
            
            // The top of the heap is the max score in the current window
            int[] top = pq.peek();
            maxScore = nums[i] + top[0];
            
            // Add the current score and index to the heap
            pq.offer(new int[]{maxScore, i});
        }
        
        return maxScore;
    }
}
```
### Algorithm
*   Initialize a max heap (Priority Queue in Java) to store pairs of `[score, index]`.
*   The heap will be ordered by score in descending order.
*   Start by adding the first element's score and index to the heap: `pq.offer(new int[]{nums[0], 0})`.
*   Initialize a variable `maxScore` to `nums[0]`.
*   Iterate from `i = 1` to `n - 1`.
*   Inside the loop, first, remove any elements from the top of the heap whose indices are outside the current window (i.e., `index < i - k`).
*   The element at the top of the heap now represents the maximum score in the valid `k`-sized window. Get this score.
*   Calculate the score for the current index `i` as `current_score = nums[i] + pq.peek()[0]`.
*   Update `maxScore = current_score`.
*   Add the new `[current_score, i]` to the heap.
*   After the loop, `maxScore` will be the result for the last index.

## DP with Deque (Sliding Window Maximum)
This approach provides the most optimal solution by using a deque to solve the sliding window maximum problem in linear time. We maintain a deque of indices such that the `dp` values corresponding to these indices are in a monotonically decreasing order. This structure allows us to find the maximum in the current window in O(1) time by simply looking at the front of the deque. Each index is added to and removed from the deque at most once, leading to an amortized O(1) time per step.
**Time:** O(N), where N is the number of elements. Each index is pushed and popped from the deque at most once, and all deque operations are O(1). · **Space:** O(K) for the deque, which stores at most `k` indices. If we modify the input array `nums` in-place, no extra space for a DP array is needed.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(K).; It's a very efficient and standard technique for sliding window problems.
**Cons:** The logic for maintaining the monotonic deque can be less intuitive than the heap-based approach for beginners.
### Explanation
The problem of finding the maximum in a sliding window can be solved most efficiently in O(N) time using a double-ended queue (deque). The deque will store indices of `nums`.

We maintain a special property in the deque: it stores indices `j1, j2, ..., jm` such that `j1 < j2 < ... < jm` and the corresponding scores `dp[j1] > dp[j2] > ... > dp[jm]`. This is a monotonically decreasing deque with respect to the scores.

As we iterate from `i = 0` to `n-1`:
1.  **Window Maintenance**: Remove indices from the front of the deque that are no longer in the current window of size `k`. That is, if `dq.front() <= i - k - 1`, remove it.
2.  **Calculate Score**: The maximum score in the window is now at `dp[dq.front()]`. We calculate the current score `dp[i] = nums[i] + dp[dq.front()]`. We can use the `nums` array itself to store the `dp` values to optimize space.
3.  **Maintain Monotonicity**: Before adding `i` to the deque, we remove all indices `j` from the back of the deque if `dp[j] <= dp[i]`. This ensures that the deque remains monotonically decreasing.
4.  **Add Index**: Add the current index `i` to the back of the deque.

This process ensures that the head of the deque always holds the index of the maximum element in the current window, and each element is processed in amortized constant time.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        // Deque stores indices of nums
        Deque<Integer> dq = new ArrayDeque<>();
        
        // Start with the first element's index
        dq.offerLast(0);
        
        for (int i = 1; i < n; i++) {
            // 1. Remove indices from the front that are out of the window [i-k, i-1]
            if (dq.peekFirst() < i - k) {
                dq.pollFirst();
            }
            
            // 2. The front of the deque has the index with the max score in the window.
            // Update nums[i] to store the max score to reach this point.
            nums[i] = nums[i] + nums[dq.peekFirst()];
            
            // 3. Maintain the monotonic decreasing property of the deque.
            // Remove indices from the back whose scores are less than the current score.
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            
            // 4. Add the current index to the deque.
            dq.offerLast(i);
        }
        
        return nums[n - 1];
    }
}
```
### Algorithm
*   Initialize a double-ended queue (deque) to store indices.
*   We will use the input array `nums` to store the DP scores to save space. `nums[i]` will be updated to hold the max score to reach index `i`.
*   Add the starting index `0` to the deque.
*   Iterate from `i = 1` to `n - 1`.
*   First, remove indices from the front of the deque that are outside the window `[i-k, i-1]`. Check if `dq.peekFirst() < i - k`.
*   The index at the front of the deque, `dq.peekFirst()`, now corresponds to the maximum score in the valid window. Update the current score: `nums[i] = nums[i] + nums[dq.peekFirst()]`.
*   To maintain the monotonic property, remove all indices from the back of the deque whose scores are less than or equal to the new score `nums[i]`.
*   Add the current index `i` to the back of the deque.
*   The final answer is `nums[n-1]`.

# Solutions
### Java

```java
class Solution {
public
  int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] f = new int[n];
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(0);
    for (int i = 0; i < n; ++i) {
      if (i - q.peekFirst() > k) {
        q.pollFirst();
      }
      f[i] = nums[i] + f[q.peekFirst()];
      while (!q.isEmpty() && f[q.peekLast()] <= f[i]) {
        q.pollLast();
      }
      q.offerLast(i);
    }
    return f[n - 1];
  }
}

```

### CPP

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

```

### Python

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