最长上升子序列

#include<bits/stdc++.h>
using namespace std; 
int a[101]={5,7,1,9,4,6,2,8,3};
int f[101]={};
int n=9;
int ans=1;
int main(){
	for(int i=1;i<=n;i++) f[i]=1;

	for(int i=2;i<n;i++){
		for(int j=1;j<i;j++)
			if(a[i]>a[j])
				f[i]=max(f[j]+1,f[i]);
			ans=max(f[i],ans);
	}
	printf("%d",ans);
	return 0;	
}

#include<bits/stdc++.h>
using namespace std; 
//int a[101]={1,2,5,9,4,6,7,1,7,2}; 1 2 5 9 4 6 7 1 7 2
								//  1 9 5 9 4 6 7 1 7 2
								//  3 9 9 9 9 9 9 9 7 8
								//  3 1 2 1 8 5 6
int a[101000];
int n;
int b[101000];
int len;
int find(int x){
	// 二分查找第一个大于等于x 的位置 
	int L=1,R=len,mid;
	while(L<R){
		mid=(L+R)/2;
		if(x>b[mid])L=mid+1;
		else R=mid-1;
	}  
	return L;
}
int main(){
	int j;
	len=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	b[1]=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]>b[len]){
			b[++len]=a[i];
		}
		else{
			j=find(a[i]);
			b[j]=a[i];
		}
	}
	printf("%d",len);
    return 0;
}