Code Implementation

class Solution:
    def maxJumps(self, arr, d):
        n = len(arr)
        dp = [0] * n

        def dfs(i):
            if dp[i]:
                return dp[i]
            max_jump = 1
            # Left
            for j in range(i-1, max(i-d-1, -1), -1):
                if arr[j] >= arr[i]:
                    break
                max_jump = max(max_jump, 1 + dfs(j))
            # Right
            for j in range(i+1, min(i+d+1, n)):
                if arr[j] >= arr[i]:
                    break
                max_jump = max(max_jump, 1 + dfs(j))
            dp[i] = max_jump
            return max_jump

        return max(dfs(i) for i in range(n))
      

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        vector<int> dp(n, 0);
        function<int(int)> dfs = [&](int i) {
            if (dp[i]) return dp[i];
            int max_jump = 1;
            // Left
            for (int j = i - 1; j >= max(i - d, 0); --j) {
                if (arr[j] >= arr[i]) break;
                max_jump = max(max_jump, 1 + dfs(j));
            }
            // Right
            for (int j = i + 1; j <= min(i + d, n - 1); ++j) {
                if (arr[j] >= arr[i]) break;
                max_jump = max(max_jump, 1 + dfs(j));
            }
            dp[i] = max_jump;
            return max_jump;
        };
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res = max(res, dfs(i));
        }
        return res;
    }
};
      

class Solution {
    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        int[] dp = new int[n];
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, dfs(arr, d, dp, i));
        }
        return res;
    }

    private int dfs(int[] arr, int d, int[] dp, int i) {
        if (dp[i] != 0) return dp[i];
        int max_jump = 1;
        // Left
        for (int j = i - 1; j >= Math.max(i - d, 0); --j) {
            if (arr[j] >= arr[i]) break;
            max_jump = Math.max(max_jump, 1 + dfs(arr, d, dp, j));
        }
        // Right
        for (int j = i + 1; j <= Math.min(i + d, arr.length - 1); ++j) {
            if (arr[j] >= arr[i]) break;
            max_jump = Math.max(max_jump, 1 + dfs(arr, d, dp, j));
        }
        dp[i] = max_jump;
        return max_jump;
    }
}
      

var maxJumps = function(arr, d) {
    const n = arr.length;
    const dp = new Array(n).fill(0);

    function dfs(i) {
        if (dp[i]) return dp[i];
        let max_jump = 1;
        // Left
        for (let j = i - 1; j >= Math.max(i - d, 0); --j) {
            if (arr[j] >= arr[i]) break;
            max_jump = Math.max(max_jump, 1 + dfs(j));
        }
        // Right
        for (let j = i + 1; j <= Math.min(i + d, n - 1); ++j) {
            if (arr[j] >= arr[i]) break;
            max_jump = Math.max(max_jump, 1 + dfs(j));
        }
        dp[i] = max_jump;
        return max_jump;
    }

    let res = 0;
    for (let i = 0; i < n; ++i) {
        res = Math.max(res, dfs(i));
    }
    return res;
};
      

Problem Description

Given an array arr of positive integers and an integer d, you start at any index and can jump left or right up to d steps. However, you can only jump to indices with a strictly lower value than your current index, and you must stop jumping in a direction if you encounter a value greater than or equal to your starting value.

Your goal is to find the maximum number of indices you can visit starting from any index, counting the starting index itself. Each index may be visited only once in each path, and you must not revisit elements.

Constraints:

• 1 ≤ arr.length ≤ 1000
• 1 ≤ arr[i] ≤ 10⁵
• 1 ≤ d ≤ arr.length

Thought Process

At first glance, the problem seems to ask for the longest path you can take by jumping from each index, following the rules. A brute-force approach would be to try every possible path from every index, but this quickly becomes inefficient as the array grows.

The key insight is that the problem exhibits overlapping subproblems: the maximum number of jumps from a given index depends only on the results from its potential next jumps. Thus, we can use memoization (dynamic programming) to store results and avoid redundant calculations.

The process is similar to exploring all possible moves in a game, but with the added restriction that you can only move to strictly lower values and must stop when you hit a higher or equal value. This makes the problem ideal for a depth-first search (DFS) with memoization.

Solution Approach

• Step 1: Define Subproblem
  For each index i, let dp[i] be the maximum number of indices you can visit starting from i.
• Step 2: Use DFS with Memoization
  Implement a recursive function that, for each index, explores all valid jumps to the left and right (within d steps), but only to strictly lower values, and stops if a higher or equal value is encountered.
• Step 3: Memoize Results
  Store the result for each index in dp[i] so that each index is only computed once, ensuring efficient computation.
• Step 4: Try All Starting Points
  Since you can start at any index, compute the maximum path length for each index and return the largest value.
• Why This Works:
  - Memoization prevents repeated work.
  - DFS ensures we explore all valid paths.
  - The constraints allow this approach to run efficiently.

Example Walkthrough

Suppose arr = [6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12] and d = 2.

• Start at index 2 (value 14):
• Left: Can jump to index 1 (4) and 0 (6), both lower than 14.
• Right: Can jump to index 3 (6) and 4 (8), both lower than 14.
• From each of these, recursively explore further valid jumps.
• For example, from index 2 to index 5 (13) is not allowed, as 13 < 14 but is out of range (d=2).
• By recursively applying the rules and memoizing, we find the maximum path length from each index. For this input, the answer is 4 (e.g., 2 → 4 → 5 → 10).

This process is repeated for each starting index, and the overall maximum is returned.

Time and Space Complexity

• Brute-force:
  Each index could potentially lead to exponential paths, making the time complexity O(2^n) in the worst case.
• Optimized (DFS + Memoization):
  Each index is visited once, and for each, we check up to 2d possible moves (left and right). Thus, the time complexity is O(n * d).
• Space Complexity:
  O(n) for the memoization array, plus O(n) for the recursion stack (in the worst case).

The approach is efficient for the given constraints.

Summary

The key to solving Jump Game V is recognizing overlapping subproblems and using memoization to avoid recomputation. By using DFS to explore all valid jumps from each index and caching results, we efficiently find the longest possible path from any starting point. This approach leverages dynamic programming principles and is both elegant and practical for the problem's constraints.