题解 | 最长不下降子序列

import java.util.Scanner;

import java.io.*;

//讲个笑话这题写地时候没用脑子
//这不就是最长严格上升子序列吗？
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int[] nums = new int[n + 1];
        //i结尾
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            nums[i] = in.nextInt();
        }
        int ans =0;
        for(int i =1;i <=n;i++){
            dp[i] = 1;
            for(int j = 1;j < i; j++){
                if(nums[j] <= nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            if(dp[i] > ans){
                ans = dp[i];
            }
        }
        out.println(ans);
        out.flush();
    }
}