Jump Game V
Problem
Given an array arr and an integer d, from index i you may jump to i ± x for 1 ≤ x ≤ d (staying in bounds) only if every bar strictly between i and the target is shorter than arr[i], and the target itself is shorter than arr[i]. Starting from any index, return the maximum number of indices you can visit.
arr = [6,4,14,6,8,13,9,7,10,6,12], d = 24def maxJumps(arr, d):
n = len(arr)
dp = [0] * n # dp[i] = best visits starting at i
order = sorted(range(n), key=lambda i: arr[i]) # shortest bars first
for i in order:
best = 0
for j in range(i + 1, min(n, i + d + 1)): # scan right
if arr[j] >= arr[i]:
break # blocked by a tall/equal bar
best = max(best, dp[j])
for j in range(i - 1, max(-1, i - d - 1), -1): # scan left
if arr[j] >= arr[i]:
break
best = max(best, dp[j])
dp[i] = 1 + best # this index plus the best reachable
return max(dp)function maxJumps(arr, d) {
const n = arr.length;
const dp = new Array(n).fill(0); // dp[i] = best visits from i
const order = [...arr.keys()].sort((a, b) => arr[a] - arr[b]);
for (const i of order) { // shortest bars first
let best = 0;
for (let j = i + 1; j < Math.min(n, i + d + 1); j++) {
if (arr[j] >= arr[i]) break; // blocked to the right
best = Math.max(best, dp[j]);
}
for (let j = i - 1; j > Math.max(-1, i - d - 1); j--) {
if (arr[j] >= arr[i]) break; // blocked to the left
best = Math.max(best, dp[j]);
}
dp[i] = 1 + best; // include i itself
}
return Math.max(...dp);
}int maxJumps(int[] arr, int d) {
int n = arr.length;
int[] dp = new int[n]; // dp[i] = best visits from i
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> arr[a] - arr[b]); // shortest first
int ans = 0;
for (int i : order) {
int best = 0;
for (int j = i + 1; j < Math.min(n, i + d + 1); j++) {
if (arr[j] >= arr[i]) break; // blocked to the right
best = Math.max(best, dp[j]);
}
for (int j = i - 1; j > Math.max(-1, i - d - 1); j--) {
if (arr[j] >= arr[i]) break; // blocked to the left
best = Math.max(best, dp[j]);
}
dp[i] = 1 + best;
ans = Math.max(ans, dp[i]);
}
return ans;
}int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
vector<int> dp(n, 0); // dp[i] = best visits from i
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(),
[&](int a, int b){ return arr[a] < arr[b]; }); // shortest first
int ans = 0;
for (int i : order) {
int best = 0;
for (int j = i + 1; j < min(n, i + d + 1); j++) {
if (arr[j] >= arr[i]) break; // blocked to the right
best = max(best, dp[j]);
}
for (int j = i - 1; j > max(-1, i - d - 1); j--) {
if (arr[j] >= arr[i]) break; // blocked to the left
best = max(best, dp[j]);
}
dp[i] = 1 + best;
ans = max(ans, dp[i]);
}
return ans;
}Explanation
Let dp[i] be the maximum number of indices you can visit if you start at index i. The answer is the largest dp[i] over all starting points.
Because every legal jump goes from a taller bar to a strictly shorter one, dp[i] only depends on dp[j] for bars shorter than arr[i]. So if we process indices in increasing order of height, every value we need is already finished when we get to i. That ordering is what turns the recursion into a clean bottom-up pass.
For each index i we scan up to d cells to the right and up to d cells to the left. The moment we meet a bar that is at least as tall as arr[i], it acts as a wall: it blocks that direction entirely, so we stop scanning there. Among all reachable shorter bars we take the best dp[j].
Then dp[i] = 1 + max(dp[j]) over reachable j (just 1 if nothing is reachable, since you can always stand on i itself).
Example: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2. The chain of indices 10 → 8 → 6 → 7 (heights 12 → 10 → 9 → 7, strictly decreasing) visits 4 cells, which is the maximum, so the answer is 4.