2407. Longest Increasing Subsequence II Hard

1/**
2 * [2407] Longest Increasing Subsequence II
3 *
4 * You are given an integer array nums and an integer k.
5 * Find the longest subsequence of nums that meets the following requirements:
6 * 
7 * 	The subsequence is strictly increasing and
8 * 	The difference between adjacent elements in the subsequence is at most k.
9 * 
10 * Return the length of the longest subsequence that meets the requirements.
11 * 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.
12 *  
13 * Example 1:
14 * 
15 * Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
16 * Output: 5
17 * Explanation:
18 * The longest subsequence that meets the requirements is [1,3,4,5,8].
19 * The subsequence has a length of 5, so we return 5.
20 * Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.
21 * 
22 * Example 2:
23 * 
24 * Input: nums = [7,4,5,1,8,12,4,7], k = 5
25 * Output: 4
26 * Explanation:
27 * The longest subsequence that meets the requirements is [4,5,8,12].
28 * The subsequence has a length of 4, so we return 4.
29 * 
30 * Example 3:
31 * 
32 * Input: nums = [1,5], k = 1
33 * Output: 1
34 * Explanation:
35 * The longest subsequence that meets the requirements is [1].
36 * The subsequence has a length of 1, so we return 1.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	1 <= nums.length <= 10^5
42 * 	1 <= nums[i], k <= 10^5
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/longest-increasing-subsequence-ii/
48// discuss: https://leetcode.com/problems/longest-increasing-subsequence-ii/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn length_of_lis(nums: Vec<i32>, k: i32) -> i32 {
54        0
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_2407() {
66    }
67}
68