# 2407 Longest Increasing Subsequence II

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

Find the longest subsequence of `nums` that meets the following requirements:

• The subsequence is strictly increasing and
• The difference between adjacent elements in the subsequence is at most `k`.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

``````Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements
because 15 - 8 = 7 is larger than 3.
``````

Example 2:

``````Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.
``````

Example 3:

``````Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i], k <= 105`

Explanation Post

 `````` 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 31 32 33 34 35 36 37 38 39 `````` ``````class SEG: """Segment Tree for finding the max of given ranges""" def __init__(self, n): self.n = n self.tree = [0] * 2 * self.n def query(self, l, r): l += self.n r += self.n ans = 0 while l < r: if l & 1: ans = max(ans, self.tree[l]) l += 1 if r & 1: r -= 1 ans = max(ans, self.tree[r]) l >>= 1 r >>= 1 return ans def update(self, i, val): i += self.n self.tree[i] = val while i > 1: i >>= 1 self.tree[i] = max(self.tree[i * 2], self.tree[i * 2 + 1]) class Solution: def lengthOfLIS(self, nums: List[int], k: int) -> int: n = max(nums) seg = SEG(n) ans = 1 for a in nums: a -= 1 pre_max = seg.query(max(0, a - k), a) ans = max(ans, pre_max + 1) seg.update(a, pre_max + 1) return ans``````