BEADSNB - Beads
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 100000, INF = 1e9 + 7;
int a[N], lis[N], lds[N], n;
void calcLIS(int a[], int n, int res[]) {
vector<int> last (n, INF);
for(int i = 0; i < n; ++i) {
res[i] = lower_bound(last.begin(), last.end(), a[i]) - last.begin();
last[res[i]] = min(last[res[i]], a[i]);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i = 0; i < n; ++i)
cin >> a[i];
reverse(a, a + n);
calcLIS(a, n, lis);
transform(a, a + n, a, negate<int>());
calcLIS(a, n, lds);
int res = 0;
for(int i = 0; i < n; ++i)
res = max(res, lis[i] + lds[i] + 1);
cout << res << endl;
return 0;
}