题解 | #Redraiment的走法#

leetcode 最长递增子序列 时间复杂度O（N^2） 动态规划 空间复杂O(N)

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int[] res=new int[a];
            for(int i=0;i<a;i++){
                res[i] = in.nextInt();
            }
            int[] dp =new int[a];
            dp[0]=1;
            int max=1;
            for(int i=1;i<dp.length;i++){
                int maxSub=1;
                for(int j=0;j<i;j++){
                    if(res[i]>res[j]){
                      maxSub=Math.max(maxSub,dp[j]+1);
                    }
                }
                dp[i]=maxSub;
                max=Math.max(max,maxSub);
            }
            System.out.println(max);
        }
    }
}