[LeetCode] Longest Increasing Subsequence II

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.

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
40
41
42
struct Seg {
int mi, ma, n;
Seg *left, *right;

Seg(vector<int>& A, int l, int r) : mi(A[l]), ma(A[r]), n(0), left(nullptr), right(nullptr) {
if(l != r) {
int m = l + (r - l) / 2;
left = new Seg(A, l, m);
right = new Seg(A, m + 1, r);
}
}

void update(int k, int v) {
if(mi <= k and k <= ma) {
n = max(n,v);
if(left) left->update(k,v);
if(right) right->update(k,v);
}
}

int query(int l, int r) {
if(l <= mi and ma <= r) return n;
if(r < mi or ma < l) return 0;
return max((left ? left->query(l,r) : 0), (right ? right->query(l,r) : 0));
}
};
class Solution {
public:
int lengthOfLIS(vector<int>& A, int k) {
int n = A.size(), res = 1;
vector<int> S = A;
sort(begin(S), end(S));
S.erase(unique(begin(S), end(S)), end(S));
Seg* seg = new Seg(S, 0, S.size() - 1);
for(int i = n - 1; i >= 0; i--) {
int now = 1 + seg->query(A[i] + 1, A[i] + k);
res = max(res, now);
seg->update(A[i], now);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/11/PS/LeetCode/longest-increasing-subsequence-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.