DP·标准题解

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N=205;
int n,mp[N],dp[N],ans=1;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>mp[i];
	}
	fill(dp+1,dp+1+n,1); //重置所有元素以自己为结尾的最长非下降子序列长度dp[i]为1
	for (int i=1;i<=n;i++){
		for (int j=1;j<i;j++){ //遍历所有在该元素之前的元素
			if (mp[j]<=mp[i]){ //如果该元素小于当前元素则比较dp[i],dp[j]大小
				dp[i]=max(dp[i],dp[j]+1);
				ans=max(ans,dp[i]);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}