#include<bits/stdc++.h>
using namespace std;
long i,n,a[10005],f[10005],j,ma;
long read()
{
	long x=0,m=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
   {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*m;
}
void write(long x) {
	if(x<0){
		putchar('-');
		write(-x);
		return;
	}
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
int main()
{
	n=read();
	for(i=1;i<=n;i++)a[i]=read();
	for(i=1;i<=n;i++)
	{
		f[i]=1;
		for(j=1;j<i;j++)
			if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
		ma=max(ma,f[i]);
	}
	cout<<ma;
	return 0;
}dp

从升级版改变的，所以会有点奇怪（升级版要输出路径）

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,b[5002][3],l,maxn=-1,i,j;
  cin>>n;
  for(i=1;i<=n;++i)
  {
  	cin>>b[i][1];
  	b[i][2]=1;
  }
  for(i=n-1;i>=1;--i)
  {
  	l=0;
  	for(j=i+1;j<=n;++j)
  	{
  	  if(b[j][1]>b[i][1]&&b[j][2]>l)
  	  l=b[j][2];
    }
	if(l>0)
	b[i][2]=l+1;
  }
  for(i=1;i<=n;++i)
  maxn=max(maxn,b[i][2]);
  cout<<maxn;
  return 0;
}

#include<bits/stdc++.h> #define int long long using namespace std; int n,a[10010],dp[10010]; signed main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ int t=0; for(int j=1;j<i;j++)if(a[i]>a[j])t=max(t,dp[j]); dp[i]=++t; } int maxn=0; for(int i=1;i<=n;i++){ maxn=max(maxn,dp[i]); } cout<<maxn; return 0; }

#include<bits/stdc++.h> #define int long long using namespace std; int n,a[10010],dp[10010]; signed main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ int t=0; for(int j=1;j<i;j++)if(a[i]>a[j])t=max(t,dp[j]); dp[i]=++t; } int maxn=0; for(int i=1;i<=n;i++){ maxn=max(maxn,dp[i]); } cout<<maxn; return 0; }

for(int i=1;i<=n;++i)
{
    dp[i]=1;
    for(int j=1;j<i;++j)
        if(a[j]<a[i])
            dp[i]=max(dp[i],dp[j]+1);
    ans=max(ans,dp[i]);
}