Longest Bounded-Step Subsequence

You are given an integer array nums and an integer k.

A subsequence of nums is obtained by deleting zero or more elements without changing the order of the ones that remain. Call a subsequence bounded-step when it satisfies both of the following:

• it is strictly increasing, so every element is greater than the one before it; and
• every adjacent pair differs by at most k.

Return the length of the longest bounded-step subsequence of nums.

A subsequence of a single element satisfies both rules vacuously, so the answer is always at least 1.

Examples

Example 1

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation: The subsequence [1,3,4,5,8] is strictly increasing and its adjacent
differences are 2, 1, 1 and 3, all at most 3, giving length 5. Extending it with
15 is not allowed because 15 - 8 = 7 exceeds k = 3.

Example 2

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation: The subsequence [4,5,8,12] is strictly increasing with adjacent
differences 1, 3 and 4, all at most 5, giving length 4.

Example 3

Input: nums = [1,5], k = 1
Output: 1
Explanation: 5 - 1 = 4 exceeds k = 1, so the two elements cannot both be used.
Any single element is a valid subsequence, so the answer is 1.