题解 | #Redraiment的走法#

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

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String line2 = scanner.nextLine();
        String[] s = line2.split(" ");
        int[] num = new int[s.length];

        for (int i = 0; i < s.length; i++) {
            num[i] = Integer.parseInt(s[i]);

        }
        int[] dp = new int[num.length];
        for (int i = 0; i < num.length; i++) {
            dp[i] = 1;
            //i 控制引入元素,引入 1个 2个 3个  4个 .....

            for (int j = i - 1; j >= 0; j--) {
//                内层循环 和前面i-1个元素逐个比较
                if (num[i] > num[j]) {
//                   更新dp值
                    dp[i] = Math.max(dp[i], dp[j] + 1);

                }

            }

        }
        int max = -1;
        for (int i = 0; i < num.length; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }

        }
        System.out.println(max);


//        6
//        2 5 1 5 4 5
//        0 1 2 3 4 5
//        dp[i] 表示以i为结尾的最长子序列的长度


//      当只有一个元素  [2]
//                  dp[0]=1


//      加入元素5 ,[2,5]
//      dp[0]=1  ,d[1]=d[0]+1=2  5比2大,所以可以在2的基础上加


//      加入元素1 ,[2,5,1]
//      dp[0]=1  ,d[1]=2   d[2]=1

//      加入元素5 ,[2,5,1,5]
//      dp[0]=1  ,d[1]=2   d[2]=1, d[3]=max{d[0]+1,d[2]+1}=2

//      加入元素4 ,[2,5,1,5,4]
//      dp[0]=1  ,d[1]=2   d[2]=1, d[3]=2, d4=max{d[0]+1,d[2]+1,}=2

//      加入元素5 ,[2,5,1,5,4,5]
//      dp[0]=1  ,d[1]=2   d[2]=1, d[3]=2, d[4]=2,d5=max{d[0]+1,d[2]+1,d[4]+1}=3
//        dp[0]=1  ,d[1]=2   d[2]=1, d[3]=2, d[4]=2,d[5]=3


    }
}