304 North Cardinal St.
Dorchester Center, MA 02124

# Longest Increasing Subsequence II LeetCode Solution

## Problem – Longest Increasing Subsequence II LeetCode Solution

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.

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 .
The subsequence has a length of 1, so we return 1.
``````

Constraints:

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

## Longest Increasing Subsequence II LeetCode Solution in Python

``````class SEG:
def __init__(self, n):
self.n = n
self.tree =  * 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, A: List[int], k: int) -> int:
n, ans = max(A), 1
seg = SEG(n)
for a in A:
a -= 1
premax = seg.query(max(0, a - k), a)
ans = max(ans, premax + 1)
seg.update(a, premax + 1)
return ans
``````

## Longest Increasing Subsequence II LeetCode Solution in C++

``````class Solution {
public:
const static int N = 100001;
array<int, 2*N> seg{};

void update(int pos, int val){ // update max
pos += N;
seg[pos] = val;

while (pos > 1) {
pos >>= 1;
seg[pos] = max(seg[2*pos], seg[2*pos+1]);
}
}

int query(int lo, int hi){ // query max [lo, hi)
lo += N;
hi += N;
int res = 0;

while (lo < hi) {
if (lo & 1) {
res = max(res, seg[lo++]);
}
if (hi & 1) {
res = max(res, seg[--hi]);
}
lo >>= 1;
hi >>= 1;
}
return res;
}

int lengthOfLIS(vector<int>& A, int k) {
int ans = 0;
for (int i = 0; i < size(A); ++i){
int l = max(0, A[i]-k);
int r = A[i];
int res = query(l, r) + 1; // best res for the current element
ans = max(res, ans);
update(A[i], res); // and update it here
}

return ans;
}
};
``````

## Longest Increasing Subsequence II LeetCode Solution in Java

``````class Solution {

int N = 100001;
int[] seg = new int[2*N];

void update(int pos, int val){  // update max
pos += N;
seg[pos] = val;

while (pos > 1) {
pos >>= 1;
seg[pos] = Math.max(seg[2*pos], seg[2*pos+1]);
}
}

int query(int lo, int hi){ // query max [lo, hi)
lo += N;
hi += N;
int res = 0;

while (lo < hi) {
if ((lo & 1)==1) {
res = Math.max(res, seg[lo++]);
}
if ((hi & 1)==1) {
res = Math.max(res, seg[--hi]);
}
lo >>= 1;
hi >>= 1;
}
return res;
}

public int lengthOfLIS(int[] A, int k) {
int ans = 0;
for (int i = 0; i < A.length; ++i){
int l = Math.max(0, A[i]-k);
int r = A[i];
int res = query(l, r) + 1; // best res for the current element
ans = Math.max(res, ans);
update(A[i], res); // and update it here
}
return ans;
}
}
``````
##### Longest Increasing Subsequence II LeetCode Solution Review:

In our experience, we suggest you solve this Longest Increasing Subsequence II LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Longest Increasing Subsequence II LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Longest Increasing Subsequence II LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions