class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
L = [(arr[i], i) for i in range(len(arr))]
L = sorted(L, key=lambda x:x[0])
n = len(arr)
dp = [1] * n
for h, i in L:
cur = 1
# 向左跳
for idx in range(i - 1, max(0, i - d)-1, -1):
if arr[idx] >= h:
break
cur = max(dp[idx]+1,cur)
# 向右跳
for idx in range(i + 1, min(n, i + d + 1)):
if arr[idx] >= h:
break
cur = max(dp[idx] + 1, cur)
dp[i] = cur
return(max(dp))
class Solution {
private:
vector<int> f;
public:
void dfs(vector<int>& arr, int id, int d, int n) {
if (f[id] != -1) {
return;
}
f[id] = 1;
for (int i = id - 1; i >= 0 && id - i <= d && arr[id] > arr[i]; --i) {
dfs(arr, i, d, n);
f[id] = max(f[id], f[i] + 1);
}
for (int i = id + 1; i < n && i - id <= d && arr[id] > arr[i]; ++i) {
dfs(arr, i, d, n);
f[id] = max(f[id], f[i] + 1);
}
}
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
f.resize(n, -1);
for (int i = 0; i < n; ++i) {
dfs(arr, i, d, n);
}
return *max_element(f.begin(), f.end());
}
};
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
seen = dict()
def dfs(pos):
if pos in seen:
return
seen[pos] = 1
i = pos - 1
while i >= 0 and pos - i <= d and arr[pos] > arr[i]:
dfs(i)
seen[pos] = max(seen[pos], seen[i] + 1)
i -= 1
i = pos + 1
while i < len(arr) and i - pos <= d and arr[pos] > arr[i]:
dfs(i)
seen[pos] = max(seen[pos], seen[i] + 1)
i += 1
for i in range(len(arr)):
dfs(i)
print(seen)
return max(seen.values())
