# Maximum jumps to reach end of Array with condition that index i can make arr[i] jumps

Maximum jumps to reach end of Array with condition that index i can make arr[i] jumpsGiven 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 jumpsAt index 3 make 7 jumpsAt index 4 make 9 jumps Input: arr[]={2, 2, 1, 2, 3, 3}Output: 8Approach: 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 loopAssign 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++#include using namespace std;  void findMaxJumps(int arr[], int N){            int dp[N] = { 0 };    int ans = 0;          for (int i = N – 1; i >= 0; i–) {        dp[i] = arr[i];        int j = i + arr[i];                          if (j < N) {                                      dp[i] = dp[i] + dp[j];        }                          ans = max(ans, dp[i]);    }          cout 