## Similar Problems

Similar Problems not available

# Jump Game Vi - Leetcode Solution

## Companies:

LeetCode: Jump Game Vi Leetcode Solution

Difficulty: Medium

Topics: dynamic-programming heap-priority-queue array

Problem Statement:

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 (index n - 1). Your score is the sum of all nums[i] for each index i you visited in the array.

Return the maximum score you can get.

Solution:

Approach:

This problem can be solved using dynamic programming. We can maintain an array dp where dp[i] represents the maximum score we can get if we reach index i. To calculate dp[i], we need to consider all the indices from i-k to i-1 that can reach i, and choose the one that gives the maximum score.

We can use a deque to maintain the indices that can reach i. We start by adding index 0 to the deque. We then iterate from index 1 to index n-1, and for each index i, we check the indices in the deque from front to back, and remove the indices that can't reach i. We then add i to the back of the deque. We then calculate dp[i] using the front of the deque. We then remove the indices from the back of the deque that can't reach i-k. Finally, we return dp[n-1].

Algorithm:

- Initialize a deque dq.
- Initialize an array dp of size n with all elements as 0.
- Add index 0 to dq.
- For i = 1 to n-1, do: a. While dq is not empty and dq front is less than i-k, remove the front element from dq. b. Calculate dp[i] as dp[dq front] + nums[i]. c. While dq is not empty and dp[dq back] <= dp[i], remove the back element from dq. d. Add i to dq.
- Return dp[n-1].

Code:

Here's the Python implementation of the above algorithm:

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

Complexity Analysis:

The time complexity of the above algorithm is O(n) because we process each index only once. The space complexity is O(n) because we use an array dp of size n and a deque that can have at most k elements.

## Jump Game Vi Solution Code

`1`