题解 | 最长不下降子序列

#include <iostream>


using namespace std;

const int N = 5e3 + 10;
int a[N];
int dp[N];


int main() {
    int n;
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        dp[i] = 1;
    }
    
    for(int i = 2;i <= n;i++){
        for(int j = 1;j < i;j++){
            if(a[i] >= a[j]){
                dp[i] = max(dp[i],dp[j] + 1);
            }
        }
    }
    int max_len = 0;
    for(int i = 1;i <= n;i++){
        max_len = max(max_len,dp[i]);
    }
    cout<<max_len<<endl;
}
// 64 位输出请用 printf("%lld")