51nod 1134 最长递增子序列 dp(经典)

第1行：1个数N，N为序列的长度(2 <= N <= 50000)第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S[i] <= 10^9)Output
输出最长递增子序列的长度。Input示例
8516824510Output示例
5
//超时代码 #include<cstdio>#include<cstring>#include<iostream>using namespace std;int main(){	int a[50001],n,dp[50001],maxx=-999999999;	scanf("%d",&n);	for(int i=1;i<=n;i++){		scanf("%d",&a[i]);		dp[i]=1;		for(int j=1;j<i;j++)		if(a[j]<a[i])		dp[i]=max(dp[i],dp[j]+1);		maxx=max(maxx,dp[i]);	}	cout<<maxx<<endl;	return 0;}
//优化后的代码 #include<cstdio>#include<iostream>using namespace std;	int n,dp[50001]={0,1e+9},len=1,t,k;int find(int num){	int low=1,mid,high=len;	while(low<=high){		mid=(high+low)/2;		if(dp[mid]==num) return mid;		if(dp[mid]>num) high=mid-1;		else low=mid+1;	}	return low;}int main(){	scanf("%d",&n);	for(int i=1;i<=n;i++){		scanf("%d",&t);		k=find(t);		if(k<=len) dp[k]=t;		else dp[++len]=t;	}	PRintf("%d/n",len);	return 0;}