345. Jump Game V

Process bars from shortest to tallest. Each bar's answer depends only on shorter reachable bars, which are already computed when we get to it.

Mental Model

Imagine each bar in a histogram. You can only jump downward to strictly shorter bars within distance d, and no taller bar can block the path. The question is: from which starting bar can you visit the most bars?

Since you always jump to shorter bars, the answer for a tall bar depends on already-computed answers for shorter bars. This gives us the DP ordering: process indices sorted by ascending bar height.

Algorithm

1. Initialize dp[i] = 1 for every index (you always visit at least yourself).
2. Sort indices by arr[i] ascending.
3. For each index i in sorted order:
   • Scan left: for x = 1, 2, ..., d, check index i - x. If arr[i - x] >= arr[i], stop (this bar blocks further jumps). Otherwise, dp[i] = max(dp[i], dp[i - x] + 1).
   • Scan right: for x = 1, 2, ..., d, check index i + x. If arr[i + x] >= arr[i], stop. Otherwise, dp[i] = max(dp[i], dp[i + x] + 1).
4. Return max(dp).

Worked Example

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

Indices sorted by value: [1(4), 0(6), 3(6), 9(6), 7(7), 4(8), 6(9), 8(10), 10(12), 5(13), 2(14)]

max(dp) = 4 at index 10. The path is 10 -> 8 -> 6 -> 7.

Edge Cases

• All equal values: No jumps possible since you need strictly smaller. Answer = 1.
• Strictly decreasing with d=1: Every bar can jump to the next. Answer = n.
• Single element: Answer = 1.

Complexity

• Time: O(n * d) — for each of n indices, we scan at most 2d neighbors.
• Space: O(n) — the dp array plus the sorted index list.

import java.util.Arrays;

class Solution {
    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> arr[a] - arr[b]);
        for (int i : order) {
            for (int x = 1; x <= d; x++) {
                int j = i - x;
                if (j < 0 || arr[j] >= arr[i]) break;
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            for (int x = 1; x <= d; x++) {
                int j = i + x;
                if (j >= n || arr[j] >= arr[i]) break;
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int ans = 0;
        for (int v : dp) ans = Math.max(ans, v);
        return ans;
    }
}