题解 | 最长不下降子序列

import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/8
 * @description BGN66 最长不下降子序列
 */
public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
	  	//dp[i]到以a[i]结尾（包含a[i]）的非减序列的最大长度, dp2[i]表示到i为止的非减序列最大长度
        int[] dp = new int[n], dp2 = new int[n];
        
        dp[0] = 1;
        dp2[1] = 1;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            for (int j = 0; j < i; j++) {
                if (a[j] <= a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            dp2[i] = i > 0 ? Math.max(dp2[i - 1], dp[i]) : 1;
        }

        System.out.println(dp[n - 1]);
    }
}