# Solution For Jump Game Vi

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.

## Step by Step Implementation For Jump Game Vi

class Solution { public int maxJumps(int[] arr, int d) { int n = arr.length; int[] dp = new int[n]; Arrays.fill(dp, 1); for(int i = 0; i < n; i++) { for(int j = i + 1; j <= Math.min(i + d, n - 1); j++) { if(arr[j] >= arr[i]) break; dp[j] = Math.max(dp[j], dp[i] + 1); } for(int j = i - 1; j >= Math.max(0, i - d); j--) { if(arr[j] >= arr[i]) break; dp[j] = Math.max(dp[j], dp[i] + 1); } } int res = 0; for(int i = 0; i < n; i++) { res = Math.max(res, dp[i]); } return res; } }

class Solution: def maxJumps(self, arr: List[int], d: int) -> int: # create a list to keep track of the maximum number of jumps # that can be made from each index in the array jumps = [0] * len(arr) # sort the array in reverse order so that we can start # from the back of the array and work our way forward sorted_arr = sorted(arr, reverse=True) # for each element in the array, starting from the back for i in range(len(sorted_arr)): # get the current element curr = sorted_arr[i] # keep track of the maximum number of jumps that can be made # from the current element max_jumps = 1 # starting from the current element, check the next d elements # to see if any jumps can be made for j in range(i+1, min(i+d+1, len(sorted_arr))): # get the next element next = sorted_arr[j] # if the next element is greater than the current element, # then a jump can be made if next > curr: # update the maximum number of jumps that can be made # from the current element max_jumps = max(max_jumps, jumps[j]+1) # update the list with the maximum number of jumps that can be made # from the current element jumps[i] = max_jumps # return the maximum number of jumps that can be made from the first element return jumps[0]

var jumpGameVI = function(arr, target) { // your code goes here };

class Solution { public: int maxJumps(vector& arr, int d) { int n = arr.size(); vector dp(n, 1); for(int i = 0; i < n; ++i) { for(int j = i + 1; j <= min(i + d, n - 1) && arr[j] < arr[i]; ++j) { dp[j] = max(dp[j], dp[i] + 1); } for(int j = i - 1; j >= max(0, i - d) && arr[j] < arr[i]; --j) { dp[j] = max(dp[j], dp[i] + 1); } } return *max_element(dp.begin(), dp.end()); } };

//This is a C# solution for the leetcode problem "Jump Game VI" //Given an array of integers arr and an integer target. //You have to jump to the target index target with the fewest jumps. //Return the number of jumps needed to reach the target. public int JumpGameVI(int[] arr, int target) { //edge case: if (arr == null || arr.Length == 0) { return -1; //error } //initialize variables: int n = arr.Length; int[] dp = new int[n]; //dp[i] = minimum number of jumps needed to reach index i dp[0] = 0; //base case //loop through the array: for (int i = 1; i < n; i++) { //initialize min jumps to reach index i as infinity: dp[i] = Int32.MaxValue; //loop through all previous indices: for (int j = 0; j < i; j++) { //if we can reach index i from index j: if (arr[j] >= i - j) { //update dp[i] with the minimum number of jumps needed: dp[i] = Math.Min(dp[i], dp[j] + 1); } } } //return the minimum number of jumps needed to reach the target index: return dp[target]; }