HDU 1950 Bridging signals(O(nlogn)算法LIS)

给出多个序列,求每个序列的最长上升子序列(LIS:Longest Increasing Subsequence)。
紫书上只给出了LIS的O(n^2)算法,百度O(nlogn)算法,顺便出了这道。遍历数组,用数组储存每个上升子序列的最小结尾。对当前数二分查找求下界,替换原
结尾。

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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=40010;
int a[maxn],ans[maxn],len;
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
ans[1]=a[1];
len=1;
for(int i=2;i<=n;++i)
if(a[i]>ans[len]) ans[++len]=a[i];
else{
int pos=lower_bound(ans,ans+len,a[i])-ans;
ans[pos]=a[i];
}
cout<<len<<endl;
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。