Given an integer N and an array arr[ ] of size N, the task is to find the maximum jumps to reach the end of the array given the constraint that from index i can make arr[i] jumps and reach the position i+arr[i].
Examples:
Input: N = 5, arr[] = {2, 3, 5, 7, 9}
Output: 12
Explanation:
At index 0 make 2 jumps and move to index 2 and make 5 jumps after that to reach index 7 which is out of the array so total number of jumps is (2+5)=7.
At index 1 make 3+9= 12 jumps
At index 2 make 5 jumps
At index 3 make 7 jumps
At index 4 make 9 jumpsInput: arr[]={2, 2, 1, 2, 3, 3}
Output: 8
Approach: The idea is to use Dynamic programming to solve this problem. Follow the steps below to solve the problem.
- Initialize an array dp of size N with 0. dp[i] stores the number of jumps needed to reach the end of the array from index i. Also, initialize an integer ans to 0.
- Traverse through the array from the end of the array using for loop
- Assign arr[i] to dp[i] since arr[i] is the smallest number of jumps from this index.
- Now initialize a variable say j and assign j = i+arr[i].
- If the value of j is less than N, then add dp[j] to dp[i].
- Update the value of ans as max(ans, dp[i])
- After completing the above steps print the value of ans.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// jumps to reach end of arrayvoid findMaxJumps(int arr[], int N){ // Stores the jumps needed // to reach end from each index int dp[N] = { 0 }; int ans = 0; // Traverse the array for (int i = N - 1; i >= 0; i--) { dp[i] = arr[i]; int j = i + arr[i]; // Check if j is less // than N if (j < N) { // Add dp[j] to the // value of dp[i] dp[i] = dp[i] + dp[j]; } // Update the value // of ans ans = max(ans, dp[i]); } // Print the value of ans cout << ans;}// Driver Codeint main(){ int arr[] = { 2, 3, 5, 7, 9 }; int N = sizeof(arr) / sizeof(arr[0]); findMaxJumps(arr, N); return 0;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Function to find the maximum// jumps to reach end of arraystatic void findMaxJumps(int arr[], int N){ // Stores the jumps needed // to reach end from each index int dp[] = new int [N]; int ans = 0; // Traverse the array for (int i = N - 1; i >= 0; i--) { dp[i] = arr[i]; int j = i + arr[i]; // Check if j is less // than N if (j < N) { // Add dp[j] to the // value of dp[i] dp[i] = dp[i] + dp[j]; } // Update the value // of ans ans = Math.max(ans, dp[i]); } // Print the value of ans System.out.println(ans);}// Driver Codepublic static void main (String[] args) { int arr[] = { 2, 3, 5, 7, 9 }; int N = arr.length; findMaxJumps(arr, N);}}// This code is contributed by Dharanendra L V. |
Python3
# python 3 code for the above approach# Function to find the maximum# jumps to reach end of arraydef findMaxJumps(arr, N): # Stores the jumps needed # to reach end from each index dp = [0 for i in range(N)] ans = 0 # Traverse the array i = N - 1 while(i >= 0): dp[i] = arr[i] j = i + arr[i] # Check if j is less # than N if (j < N): # Add dp[j] to the # value of dp[i] dp[i] = dp[i] + dp[j] # Update the value # of ans ans = max(ans, dp[i]) i -= 1 # Print the value of ans print(ans)# Driver Codeif __name__ == '__main__': arr = [2, 3, 5, 7, 9] N = len(arr) findMaxJumps(arr, N) # This code is contributed by ipg2016107. |
C#
// C# code for the above approachusing System;class GFG { // Function to find the maximum // jumps to reach end of array static void findMaxJumps(int[] arr, int N) { // Stores the jumps needed // to reach end from each index int[] dp = new int[N]; int ans = 0; // Traverse the array for (int i = N - 1; i >= 0; i--) { dp[i] = arr[i]; int j = i + arr[i]; // Check if j is less // than N if (j < N) { // Add dp[j] to the // value of dp[i] dp[i] = dp[i] + dp[j]; } // Update the value // of ans ans = Math.Max(ans, dp[i]); } // Print the value of ans Console.Write(ans); } // Driver Code public static void Main(string[] args) { int[] arr = { 2, 3, 5, 7, 9 }; int N = arr.Length; findMaxJumps(arr, N); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript code for the above approach// Function to find the maximum// jumps to reach end of arrayfunction findMaxJumps(arr, N) { // Stores the jumps needed // to reach end from each index let dp = new Array(N).fill(0); let ans = 0; // Traverse the array for (let i = N - 1; i >= 0; i--) { dp[i] = arr[i]; let j = i + arr[i]; // Check if j is less // than N if (j < N) { // Add dp[j] to the // value of dp[i] dp[i] = dp[i] + dp[j]; } // Update the value // of ans ans = Math.max(ans, dp[i]); } // Print the value of ans document.write(ans);}// Driver Codelet arr = [2, 3, 5, 7, 9];let N = arr.length;findMaxJumps(arr, N);// This code is contributed by _saurabh_jaiswal.</script> |
Output
12
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
