#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int k[1005];
int ans;
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	fill(k,k+n,1);
	for(int i=1;i<n;i++) for(int j=0;j<i;j++) if(a[i]>a[j]) k[i]=max(k[i],k[j]+1);
	for(int i=0;i<n;i++) ans=max(ans,k[i]);
	cout<<"Max="<<ans<<"\n";
	return 0;
}

比凌短

AC代码（From 一本通）

//b[i][1]表示第i个数的数值本身 
//b[i][2]表示从i位置到n的最长不下降序列的长度 
//b[i][3]表示从i位置开始最长不下降序列的下一个位置 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,i,j,l,k,b[200][10];//some 变量 
	cin>>n;//输入 
	for(i=1;i<=n;i++)//循环输入 
	{
		cin>>b[i][1];
		b[i][2]=1;b[i][3]=0;
	}
	for(i=n-1;i>=1;i--) //求序列 
	{
		l=0;k=0;
		for(j=i+1;j<=n;j++)
			if((b[j][1]>=b[i][1])&&(b[j][2]>l))//若上一个数大于下一个数且后面还有不下降序列 
			{
				l=b[j][2];//用l变量存储下面序列的长度
				k=j;//将j的值(即前面不下降子序列的长度)赋值给k 
			}
			if(l>0)
			{
				b[i][2]=l+1;//把i加上，重置 
				b[i][3]=k; //下一个位置即为k; 
			}
	}
	k=1;
	for(j=1;j<=n;j++)//求最长不下降序列的起始位置 
		if(b[j][2]>b[k][2])k=j;//若前方还有更大的，则重置起始位置
	cout<<"Max="<<b[k][2]<<endl;//输入最长不下降序列
}