题目描述
最长上升子序列
样例
blablabla
算法1
(dp优化) $O(nlog2n)$
维护一个数组di[]记录长度为i的上升子序列的末尾最小值
len为最长子序列长度
当加入一个数,如果比di[len]大,len++并更新di[len]
如果一样丢掉
如果小的话找到第一个比new大的d[i]并替换
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define MAXNB 200005
#define MAXNP 10005
#define MAXN 105
int n,m,l,r,arr[MAXN];
int main(){
cin>>n;
while(n--){
cin>>m;
int di[m];
int len1=1,len2=1;
for(int i=1;i<=m;i++){
cin>>arr[i];
if(i==1){
di[1]=arr[i];
}
if(di[len1]<arr[i]){
di[++len1]=arr[i];
}else if(di[len1]>arr[i]){
// cout<< lower_bound(di+1,di+len1+1,arr[i])-di <<endl;
di[lower_bound(di+1,di+len1+1,arr[i])-di]=arr[i];
}
}
for(int i=m;i>=1;i--){
if(i==m){
di[1]=arr[i];
}
if(di[len2]<arr[i]){
di[++len2]=arr[i];
}else if(di[len2]>arr[i]){
// cout<< lower_bound(di+1,di+len2+1,arr[i])-di <<endl;
di[lower_bound(di+1,di+len2+1,arr[i])-di]=arr[i];
}
}
cout<<max(len1,len2)<<endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla