最長上昇サブシーケンスnlogn
2566 ワード
fiはi長の上昇サブシーケンスの最小末尾要素値を表す貪欲な方法で,現在の末尾値より小さい要素にアクセスするたびに,置換可能な位置を2分前に探す.
#include
#include
#include
#include
using namespace std;
#define debug(x) cerr << #x << "=" << x << endl;
const int MAXN = 100000 + 10;
int f[MAXN],n,a[MAXN],vis[MAXN];
int q,fa[MAXN],last[MAXN],depth[MAXN],len;
int find(int x) {
int l=1, r=len;
int ans;
while(l<=r) {
int mid = l+r>>1;
if(f[mid] > x) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin >> a[i];
}
f[1] = a[1];
len = 1;
for(int i=2; i<=n; i++) {
if(a[i] > f[len]) f[++len] = a[i];
else {
int temp = find(a[i]);
f[temp] = a[i];
}
}
cout << len;
return 0;
}