题解 | #Redraiment的走法#

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
            count(arr);
        }
    }
    private static void count(int[] arr) {
        int[] countArr = new int[arr.length];
        Arrays.fill(countArr, 1);
        int max = 1;

        // 以索引1结尾，求最长子序列，存入countArr[1]
        // 当以2结尾时，就可以取1的最长子序列作为参考(这就是动态规划的核心-取前面的累计值作为参考)
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    // countArr[j]表示目前截止j处最长子序列，那么countArr[i]最长就是countArr[j]，
                    // 而arr[j] < arr[i]，那么countArr[i]就+1，反之countArr[i]不变
                    countArr[i] = Math.max(countArr[j] + 1, countArr[i]);
                }
                max = Math.max(max, countArr[i]);
            }
        }
        System.out.println(max);
    }
}