/*
bupt 1032
nlogn LIS
注意!
是最长不减序列(*1),而非最长升序列(*2)
则当t>=D[len]就直接更新len+1
而t<D[len]时,应在D[1..len]中查找最大的j,满足D[j]<=A[t](在*2中,是满足D[j]<A[t]),
将t接在D[j]后得到更长的不减序列,同时更新D[j+1]=t
这是我WA很多次的地方.对这个算法未理解透彻
附一组原先错误程序WA的数据:
40
9 7 10 13 18 4 13 37 24 7 30 17 36 20 23 26 35 16 7 25 7 30 39 3 9 11 14 8 29 35 35 17 6 11 25 25 21 17 32 38
答案12
*/
#include <iostream>
using namespace std;
int T,N,m,cnt,r[50010];
int main(){
int i,j,k;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
cnt=0; r[0]=-1;
for(i=1;i<=N;i++){
scanf("%d",&m);
if(m>=r[cnt]){ //not '>'
r[++cnt]=m;
}
else{
int bl=1,bh=cnt,bm;
k=-1;
while(bl<=bh){
bm=(bl+bh)/2;
if(r[bm]>m){ //not '>='
bh=bm-1;
k=bm;
}
else bl=bm+1;
}
r[k]=m;
}
}
printf("%d\n",cnt);
}
return 0;
}
posted on 2009-03-27 13:23
wolf5x 阅读(108)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc