TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 2526,3 "name": "longest_increasing_subsequence_ii",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/longest-increasing-subsequence-ii/",6 "date": "1662249600000",7 "task_description": "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`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [4,2,1,4,3,4,5,8,15], k = 3",12 "output": "5 "13 },14 {15 "label": "Example 2",16 "input": "nums = [7,4,5,1,8,12,4,7], k = 5",17 "output": "4 "18 },19 {20 "label": "Example 3",21 "input": "nums = [1,5], k = 1",22 "output": "1 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 9,30 12,31 13,32 16,33 17,34 28,35 29,36 30,37 34,38 40,39 44,40 45,41 57,42 6543 ],44 9745 ],46 "output": 1447 },48 {49 "input": [50 [51 2,52 4,53 16,54 27,55 40,56 43,57 48,58 55,59 60,60 82,61 87,62 91,63 98,64 9965 ],66 7567 ],68 "output": 1469 },70 {71 "input": [72 [73 20,74 27,75 42,76 51,77 52,78 57,79 64,80 66,81 76,82 77,83 81,84 89,85 95,86 10087 ],88 4589 ],90 "output": 1491 },92 {93 "input": [94 [95 14,96 28,97 8198 ],99 96100 ],101 "output": 3102 },103 {104 "input": [105 [106 3,107 19,108 28,109 30,110 32,111 47,112 63,113 64,114 69,115 80,116 94,117 95118 ],119 33120 ],121 "output": 12122 },123 {124 "input": [125 [126 4,127 5,128 18,129 26,130 33,131 41,132 42,133 62,134 69,135 73,136 75,137 76,138 78,139 80,140 87,141 96,142 97,143 98,144 99145 ],146 39147 ],148 "output": 19149 },150 {151 "input": [152 [153 65,154 94155 ],156 18157 ],158 "output": 1159 },160 {161 "input": [162 [163 64,164 95165 ],166 92167 ],168 "output": 2169 },170 {171 "input": [172 [173 8,174 15,175 16,176 21,177 27,178 29,179 47,180 59,181 67,182 68,183 93,184 98185 ],186 5187 ],188 "output": 3189 },190 {191 "input": [192 [193 9,194 32,195 35,196 49,197 53,198 65,199 69,200 79,201 83,202 87,203 89204 ],205 86206 ],207 "output": 11208 }209 ],210 "haskell_template": "lengthOfLIS :: [Int] -> Int -> Int\nlengthOfLIS nums k ",211 "ocaml_template": "let lengthOfLIS (nums: int list) (k: int) : int = ",212 "scala_template": "def lengthOfLIS(nums: List[Int],k: Int): Int = { \n \n}",213 "java_template": "public static int lengthOfLIS(List<Integer> nums, int k) {\n\n}",214 "python_template": "class Solution(object):\n def lengthOfLIS(self, nums, k):\n \"\"\"\n :type nums: List[int]\n :type k: int\n :rtype: int\n \"\"\"\n "215}