题目链接:zoj2136
讲当前最长上升子序列建一个数组,利用二分查找
#include<iostream> using namespace std; const int maxn = 1002; int a[maxn]; int find(int *a,int len,int n) { int left = 0,right=len,mid=(left+right)/2; while(left<=right) { if(a[mid] < n) left = mid + 1; else if(a[mid] > n) right = mid - 1; else return mid; mid = (left+right)/2; } return left; } int main(void) { int ncases,n; cin>>ncases; while(ncases--) { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; int c[n+1]; c[0] = -1; c[1] = a[0]; int len = 1; for(int i=1;i<n;i++) { int j = find(c,len,a[i]); c[j] = a[i]; if(j > len) len = j; } cout<<len<<endl; if(ncases) cout<<endl; } return 0; }