题解 | 最长上升子序列(一)

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int []arr = new int[n];
        int []dp = new int[n];
        Arrays.fill(dp, 1);//一个元素的序列默认是上升的
        // 注意 hasNext 和 hasNextLine 的区别
        for(int i=0;in.hasNextInt();++i) { // 注意 while 处理多个 case
            arr[i] = in.nextInt();            
        }
        for(int i=1;i<n;++i) { 
            for(int j=0;j<i;++j){
                if(arr[i]>arr[j]){// 对下一个更大的元素，从前面所记录的最长上升子序列中找
                    dp[i] = Math.max(dp[i], dp[j]+1);//然后包含下一个更大的元素
                }
            }
        }
        int maxL = Integer.MIN_VALUE;
        for(int i=0;i<n;++i){
            maxL = Math.max(maxL, dp[i]);
        }
        System.out.println(maxL);
    }

}