题解 | #Redraiment的走法#最长递增子序列，动规

import java.util.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        /**
        动态规划
        关键是想到 d[i] 的定义： 以第 i 个桩位最后一个踩的桩，的情况下的最长步数
        - d[i]是完整的一次走桩
        */

        int count = in.nextInt();
        int[] zhuangs = new int[count];
        for (int i = 0; i < count; i++) {
            zhuangs[i] = in.nextInt();
        }

        int maxSteps = 0;
        int[] d = new int[count];
        // 初始化动态规划数组
        d[0] = 1;

        for (int i = 1; i < count; i++) {
            // 初始化动态规划数组
            d[i] = 1;
            // 尝试续上之前走过的桩，zhuangs[i] > zhuangs[j]才能续上
            for (int j = 0; j < i; j++) {
                if (zhuangs[i] > zhuangs[j]) {
                    d[i] = Math.max(d[i], d[j]+1);
                }
            }
            maxSteps = Math.max(maxSteps, d[i]);
        }

        System.out.println(maxSteps);
    }
}