信息学奥赛一本通T1259-求最长不下降序列-题解（Java代码）

参考代码:

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        String[] b = new String[n];//存储路径
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 0; i < b.length; i++) {
            b[i] = a[i] + "";
        }
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < dp.length; i++) {
            int cnt = 1;
            int index = i;
            for (int j = i - 1; j >= 0; j--) {
                if (a[i] >= a[j]) {
                    if (cnt < dp[j] + 1) {
                        cnt = dp[j] + 1;
                        index = j;
                    }
                }
            }
            dp[i] = cnt;
            if (i != index)
                b[i] = b[index] + " " + b[i];
        }
        int index = 0;
        for (int i = 0; i < dp.length; i++) {
            if (max < dp[i]) {
                max = dp[i];
                index = i;
            }
        }

        System.out.println("max=" + max);
        System.out.println(b[index]);

    }
}