1.dfs写法（约n<20可用）

#include<bits/stdc++.h>
using namespace std;
int a[10005],n,dp[10005],ans=0;
void dfs(int k,int p){
	if(p>n)return;
	for(int i=p;i<=n;i++){
		if(a[i]>=dp[k-1]){
			dp[k]=a[i];
			ans=max(ans,k);
			dfs(k+1,i+1);
		}
	} 
}
int main(){
	cin>>n;
	dp[0]=INT_MIN;
	for(int i=1;i<=n;i++)cin>>a[i];
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}

2.dp

#include<bits/stdc++.h>
using namespace std;
int a[10005],n,dp[10005],ans=0;
int main(){
	cin>>n;
	dp[1]=-0x3f;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	for(int j=1;j<i;j++)
	if(a[j]<=a[i])dp[i]=max(dp[i],dp[j]+1);
	for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

3.dp(O(nlogn))写法

#include<bits/stdc++.h>
using namespace std;
int a[1000005],n,dp[1000005],k=0;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	dp[1]=a[1];
	for(int i=1;i<=n;i++){
		if(a[i]>=dp[k]){
			k++;
			dp[k]=a[i];
		}else{
			int l=upper_bound(dp+1,dp+k+1,a[i])-dp;
			dp[l]=a[i];
		}
	}
	cout<<k;
	return 0;
}