AcWing 896. 最长上升子序列 II
原题链接
中等
#include<iostream>
#include<vector>
using namespace std;
const int N = 100000+10;
int a[N];
int n;
int main(void) {
scanf("%d", &n);
for(int i=1;i<=n;++i)
scanf("%d", a+i);
vector<int > seq;
seq.push_back(a[1]);
for(int i=2;i<=n;++i) {
if(seq.back() < a[i]) seq.push_back(a[i]);
else {
int l=0,r = seq.size()-1;
while(l<r) {
int mid = l+r >>1;
if(seq[mid] >= a[i]) r = mid;
else l = mid+1;
}
//因为最长上升子序列是 seq.size(), 这里替换前面的元素,不会影响 这个 seq.size()
seq[r] = a[i];
}
}
cout << seq.size() <<endl;
return 0;
}