Untitled

import java.util.Arrays;

public class MaxJumps {
    private int[] memo; // Memoization table

    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        memo = new int[n];
        Arrays.fill(memo, -1); // Initialize memoization table with -1

        int result = 0;

        // Try starting from every index and find the maximum jumps
        for (int i = 0; i < n; i++) {
            result = Math.max(result, helper(arr, d, i));
        }

        return result;
    }

    private int helper(int[] arr, int d, int i) {
        // If already computed, return the result from memo
        if (memo[i] != -1) {
            return memo[i];
        }

        // Base case: At least the current index is visited
        int maxJumps = 1;

        // Try jumping forward (i + x)
        for (int x = 1; x <= d; x++) {
            int j = i + x;
            if (j >= arr.length || arr[j] >= arr[i]) {
                break; // Stop if out of bounds or height constraint violated
            }
            maxJumps = Math.max(maxJumps, 1 + helper(arr, d, j));
        }

        // Try jumping backward (i - x)
        for (int x = 1; x <= d; x++) {
            int j = i - x;
            if (j < 0 || arr[j] >= arr[i]) {
                break; // Stop if out of bounds or height constraint violated
            }
            maxJumps = Math.max(maxJumps, 1 + helper(arr, d, j));
        }

        // Store the result in the memo table
        memo[i] = maxJumps;

        return maxJumps;
    }

    public static void main(String[] args) {
        MaxJumps solution = new MaxJumps();

        // Example 1
        int[] arr1 = {6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12};
        int d1 = 2;
        System.out.println(solution.maxJumps(arr1, d1)); // Output: 4

        // Example 2
        int[] arr2 = {3, 3, 3, 3, 3};
        int d2 = 3;
        System.out.println(solution.maxJumps(arr2, d2)); // Output: 1

        // Example 3
        int[] arr3 = {7, 6, 5, 4, 3, 2, 1};
        int d3 = 1;
        System.out.println(solution.maxJumps(arr3, d3)); // Output: 7
    }
}