题解 | #Redraiment的走法#

dp的含义是当前位置i跟它前面的所有位置数据作比较，看位置i的值跟位置j的值是否符合递增，符合则dp按照下面的规则取值。

注意dp的初始化数据就是每一个位置在不比较的情况下，需要记录的数字，为啥是1呢，因为不走你就站上去也算是有一步了。

当前位置i跟前面小于i的所有位置数字作比较，如果符合底递增，则当前位置i的值有两种选择

第一种是保留dp当前位置的值

第二种是取位置j的值+1；

空间复杂度O(n)

时间O(n*n)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = Integer.parseInt(in.nextLine());
        String[] s = in.nextLine().split(" ");

        int[] dp = new int[n+1];

        for(int i=0;i<dp.length;i++){
            dp[i]= 1;
        }

        int result=0;
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<i;j++){
                if(Integer.parseInt(s[i-1]) > Integer.parseInt(s[j-1])){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                    result=Math.max(result,dp[i]);

                }
            }

        }
        System.out.println(result);
    }
}