题解 | 最长不下降子序列-Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        System.out.println(longestNonDecreasingSubsequence(a, n));
        scanner.close();
    }

    /**
     * 计算最长不下降子序列的长度
     * @param a 输入数组
     * @param n 数组长度
     * @return 最长不下降子序列的长度
     */
    private static int longestNonDecreasingSubsequence(int[] a, int n) {
        // 边界情况处理
        if (n == 0) {
            return 0;
        }

        // dp[i]表示以第i个元素结尾的最长不下降子序列的长度
        int[] dp = new int[n];

        // 初始化：每个元素自身可以构成一个长度为1的子序列
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        // 动态规划计算
        for (int i = 1; i < n; i++) {
            // 检查所有在i之前的元素j
            for (int j = 0; j < i; j++) {
                // 如果a[j] <= a[i]，说明可以将a[i]添加到以a[j]结尾的子序列后
                if (a[j] <= a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 找到dp数组中的最大值，即为最长不下降子序列的长度
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }

        return maxLength;
    }
}