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

总结：
计算i处的最长升序子序列len[i]，等于i之前所有的子序列（末尾元素大于arr[i])中最大子序列+1
根据上述状态转换使用动态规划解决该问题。

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();
        }
        int[] len = new int[n];//最长上升序列长度
        Arrays.fill(len,1);
        int max = 0;
        for(int i=1;i<n;i++){
            max = 0;
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    max = Math.max(max,len[j]);
                }
            }
            len[i] = max+1;
        }
        int res = 0;
        for(int i=0;i<n;i++)
            res = Math.max(res,len[i]);
        System.out.println(res);
    }
}