1340. Jump Game V

/**
 * Problem: LeetCode 1340 - Jump Game V
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        int[] memo = new int[n];
        int maxVisited = 0;

        for (int i = 0; i < n; i++) {
            maxVisited = Math.max(maxVisited, dfs(arr, d, i, memo));
        }

        return maxVisited;
    }

    private int dfs(int[] arr, int d, int i, int[] memo) {
        if (memo[i] != 0) {
            return memo[i];
        }

        int n = arr.length;
        int res = 1;

        // Jump to the right: i + 1, ..., i + d
        for (int j = i + 1; j <= Math.min(i + d, n - 1); j++) {
            if (arr[j] >= arr[i]) {
                break; // Blocked by equal or taller bar
            }
            res = Math.max(res, 1 + dfs(arr, d, j, memo));
        }

        // Jump to the left: i - 1, ..., i - d
        for (int j = i - 1; j >= Math.max(i - d, 0); j--) {
            if (arr[j] >= arr[i]) {
                break; // Blocked by equal or taller bar
            }
            res = Math.max(res, 1 + dfs(arr, d, j, memo));
        }

        return memo[i] = res;
    }
}

"""
Problem: LeetCode 1340 - Jump Game V
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        memo = [0] * n

        def dfs(i: int) -> int:
            if memo[i]:
                return memo[i]

            res = 1

            # Jump rightwards: i + 1, ..., i + d
            for j in range(i + 1, min(i + d + 1, n)):
                if arr[j] >= arr[i]:
                    break
                res = max(res, 1 + dfs(j))

            # Jump leftwards: i - 1, ..., i - d
            for j in range(i - 1, max(i - d - 1, -1), -1):
                if arr[j] >= arr[i]:
                    break
                res = max(res, 1 + dfs(j))

            memo[i] = res
            return res

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

/**
 * Problem: LeetCode 1340 - Jump Game V
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        vector<int> memo(n, 0);
        int maxVisited = 0;

        for (int i = 0; i < n; ++i) {
            maxVisited = max(maxVisited, dfs(arr, d, i, memo));
        }

        return maxVisited;
    }

private:
    int dfs(const vector<int>& arr, int d, int i, vector<int>& memo) {
        if (memo[i] != 0) {
            return memo[i];
        }

        int n = arr.size();
        int res = 1;

        // Jump rightwards: i + 1, ..., i + d
        for (int j = i + 1; j <= min(i + d, n - 1); ++j) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = max(res, 1 + dfs(arr, d, j, memo));
        }

        // Jump leftwards: i - 1, ..., i - d
        for (int j = i - 1; j >= max(i - d, 0); --j) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = max(res, 1 + dfs(arr, d, j, memo));
        }

        return memo[i] = res;
    }
};

/**
 * Problem: LeetCode 1340 - Jump Game V
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} arr
 * @param {number} d
 * @return {number}
 */
var maxJumps = function(arr, d) {
    const n = arr.length;
    const memo = new Int32Array(n);

    const dfs = (i) => {
        if (memo[i] !== 0) {
            return memo[i];
        }

        let res = 1;

        // Jump rightwards: i + 1, ..., i + d
        for (let j = i + 1; j <= Math.min(i + d, n - 1); j++) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = Math.max(res, 1 + dfs(j));
        }

        // Jump leftwards: i - 1, ..., i - d
        for (let j = i - 1; j >= Math.max(i - d, 0); j--) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = Math.max(res, 1 + dfs(j));
        }

        memo[i] = res;
        return res;
    };

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

    return maxVisited;
};