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
43
44
45
46
47
48
49
50
| struct Seg {
int mi, ma, less, greater;
Seg *left, *right;
Seg(vector<int>& A, int l, int r) : mi(A[l]), ma(A[r]), less(0), greater(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 n, int k) {
if(mi <= n and n <= ma) {
less = max(less, k);
if(left) left->update(n,k);
if(right) right->update(n,k);
}
}
int query(int n) {
if(ma < n) return less;
if(mi <= n and n <= ma) return max((left ? left->query(n) : 0), (right ? right->query(n) : 0));
return 0;
}
};
int Solution::longestSubsequenceLength(const vector<int> &A) {
if(A.empty()) return 0;
vector<int> S = A;
S.push_back(INT_MIN);
S.push_back(INT_MAX);
sort(begin(S), end(S));
S.erase(unique(begin(S), end(S)), end(S));
Seg* seg1 = new Seg(S,0,S.size() - 1);
Seg* seg2 = new Seg(S,0,S.size() - 1);
int res = 0;
vector<int> inc(A.size()), dec(A.size());
for(int i = 0; i < A.size(); i++) {
inc[i] = seg1->query(A[i]) + 1;
seg1->update(A[i], inc[i]);
}
for(int i = A.size() - 1; i >= 0; i--) {
dec[i] = seg2->query(A[i]) + 1;
seg2->update(A[i], dec[i]);
}
for(int i = 0; i < A.size(); i++) res = max(res, inc[i] + dec[i] - 1);
return res;
}
|
