Show problems as
Classic problem #2407HardArrayDivide and ConquerDynamic ProgrammingBinary Indexed TreeSegment TreeQueueMonotonic Queue

Longest Increasing Subsequence II

Real-world version: Longest Rising Run Under a Step Cap
Tracked in this browser only
Read Longest Increasing Subsequence II on LeetCode(opens in a new tab)

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

Gauge readings are given as nums. A climb picks readings from the list, keeping their order, so that every reading is strictly larger than the one before it while the rise from one to the next is never more than k.

Return how many readings the longest climb holds.

Examples

Example 1

Input
nums = [13, 6, 19, 7, 21, 8, 25], k = 7
Output
4

The climb 6, 7, 8 rises by one each time, and no longer climb keeps every step inside seven: reaching 13 then 19 is a step of six but 19 to 21 to 25 cannot be extended back far enough to beat three.

Example 2

Input
nums = [1, 3, 5, 7, 9], k = 2
Output
5

Each reading is two above the last, which the cap just allows, so the whole list is one climb.

Example 3

Input
nums = [1, 3, 5, 7, 9], k = 1
Output
1

Every step is two, which the cap forbids, so no climb holds more than one reading.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^5

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 length_of_l_i_s(nums: list[int], k: int) -> int:
Java
public int lengthOfLIS(int[] nums, int k)

More on the same topics