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

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        
        System.out.println(lengthLIS(arr));
    }
        
       // 以下代码是 最长上升子序列(一) 的具体实现
       public static int lengthLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] a = new int[nums.length];
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            a[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    a[i] = Math.max(a[i], a[j]+1);
                }
            }
            res = Math.max(res, a[i]);
        }
        return res;
    }
}