AcWing 896. 最长上升子序列 II 用STL的最简单写法
原题链接
中等
作者:
Lupinus
,
2021-08-26 17:40:07
,
所有人可见
,
阅读 235
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n;
int main() {
memset(f, 0x3f, sizeof f);
cin >> n;
// lower/upper_bound时填f+n的话,如果给出全递增序列,空间会差一个,因为是从1开始的。
// 可以填f+n+2,要保留一个0x3f3f3f3f
for (int i = 1; i <= n; ++i) {
int ai; cin >> ai;
// lower_bound会找出第一个>=ai的f[j]
* lower_bound(f + 1, f + N, ai) = ai;
}
int res = lower_bound(f + 1, f + N, 0x3f3f3f3f) - f - 1;
cout << res << endl;
return 0;
}