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 jumpsÂInput: 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 approachÂ
import 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 approachÂ
using 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!
… [Trackback]
[…] Here you will find 70561 more Information to that Topic: geeksforgeeks.org/maximum-jumps-to-reach-end-of-array-with-condition-that-index-i-can-make-arr-i-jumps/ […]
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/maximum-jumps-to-reach-end-of-array-with-condition-that-index-i-can-make-arr-i-jumps/ […]
… [Trackback]
[…] Here you can find 20147 additional Information on that Topic: geeksforgeeks.org/maximum-jumps-to-reach-end-of-array-with-condition-that-index-i-can-make-arr-i-jumps/ […]