Show problems as
Classic problem #1340HardArrayDynamic ProgrammingSorting

Jump Game V

Real-world version: Longest Descent Run
Tracked in this browser only
Read Jump Game V on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A climbing wall has a row of ledges. height[i] is the height of the ledge at position i, and a climber can hop between ledges along the row.

Standing on ledge i, the climber may hop to ledge j when all three hold:

  • j is a different position with |i - j| <= reach;
  • height[j] < height[i], so every hop goes strictly downwards;
  • every ledge strictly between i and j is also lower than height[i], so nothing on the way blocks the hop.

The climber picks any ledge to start on and then hops as many times as they like, possibly not at all. Return the largest number of ledges a single run can touch, counting the ledge it starts on.

Examples

Example 1

Input
height = [10, 1, 9], reach = 2
Output
3

Starting on the ledge of height 10, the climber hops two places right to the ledge of height 9, since 9 is lower than 10 and the ledge of height 1 in between is lower too, and then hops back one place left to the ledge of height 1. That run touches three ledges.

Example 2

Input
height = [4, 4, 4, 4], reach = 2
Output
1

No hop is legal, because no ledge is strictly lower than another. A run therefore touches only the ledge it starts on.

Example 3

Input
height = [5, 5, 5, 1, 5, 5, 5], reach = 3
Output
2

Starting on the ledge at position 2, the climber hops one place right onto the ledge of height 1. That run touches two ledges.

Constraints

  • 1 <= height.length <= 1000
  • 1 <= height[i] <= 10^5
  • 1 <= reach <= height.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_descent_run(height: list[int], reach: int) -> int:
Java
public int longestDescentRun(int[] height, int reach)

More on the same topics