# 1340. Jump Game V

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: int maxJumps(vector& arr, int d) { const int n = arr.size(); // dp[i] := max jumps starting from arr[i] vector dp(n, 1); // Decreasing stack stores indices stack stack; for (int i = 0; i <= n; ++i) { while (!stack.empty() && (i == n || arr[stack.top()] < arr[i])) { vector indices{stack.top()}; stack.pop(); while (!stack.empty() && arr[stack.top()] == arr[indices[0]]) indices.push_back(stack.top()), stack.pop(); for (const int j : indices) { if (i < n && i - j <= d) // Can jump from i to j dp[i] = max(dp[i], dp[j] + 1); if (!stack.empty() && j - stack.top() <= d) // Can jump from stack.top() to j dp[stack.top()] = max(dp[stack.top()], dp[j] + 1); } } stack.push(i); } return *max_element(dp.begin(), dp.end()); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public int maxJumps(int[] arr, int d) { final int n = arr.length; // dp[i] := max jumps starting from arr[i] int[] dp = new int[n]; // Decreasing stack stores indices Deque stack = new ArrayDeque<>(); for (int i = 0; i <= n; ++i) { while (!stack.isEmpty() && (i == n || arr[stack.peek()] < arr[i])) { List indices = new ArrayList<>(Arrays.asList(stack.pop())); while (!stack.isEmpty() && arr[stack.peek()] == arr[indices.get(0)]) indices.add(stack.pop()); for (final int j : indices) { if (i < n && i - j <= d) // Can jump from i to j dp[i] = Math.max(dp[i], dp[j] + 1); if (!stack.isEmpty() && j - stack.peek() <= d) // Can jump from stack.peek() to j dp[stack.peek()] = Math.max(dp[stack.peek()], dp[j] + 1); } } stack.push(i); } return Arrays.stream(dp).max().getAsInt() + 1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def maxJumps(self, arr: List[int], d: int) -> int: n = len(arr) # dp[i] := max jumps starting from arr[i] dp = [1] * n # Decreasing stack stores indices stack = [] for i in range(n + 1): while stack and (i == n or arr[stack[-1]] < arr[i]): indices = [stack.pop()] while stack and arr[stack[-1]] == arr[indices[0]]: indices.append(stack.pop()) for j in indices: if i < n and i - j <= d: # Can jump from i to j dp[i] = max(dp[i], dp[j] + 1) if stack and j - stack[-1] <= d: # Can jump from stack[-1] to j dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1) stack.append(i) return max(dp)