2407. Longest Increasing Subsequence II
Hard26.0% acceptance23,672 / 90,873 submissions
Asked by 1 company
Topics
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 <= 1051 <= nums[i], k <= 105
Hints
Hint 1
We can use dynamic programming. Let dp[i][val] be the answer using only the first i + 1 elements, and the last element in the subsequence is equal to val.
Hint 2
The only value that might change between dp[i - 1] and dp[i] are dp[i - 1][val] and dp[i][val].
Hint 3
Try using dp[i - 1] and the fact that the second last element in the subsequence has to fall within a range to calculate dp[i][val].
Hint 4
We can use a segment tree to find the maximum value in dp[i - 1] within a certain range.