实际上就是一个最长上升子序列的问题：设dp[i]为数组arr从0到i的最长上升子序列的长度，那么dp[i] = max(dp[j]+1,dp[i]);其中，j是从i开始向前寻找的每个满足arr[j]<arr[i]的元素。

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int arr[] = new int[n];

            for(int i = 0;i<n;++i){
                arr[i] = sc.nextInt();
            }
            int dp[] = new int[n];
            int max = 1;
            Arrays.fill(dp,1);
            for(int i = 1;i<n;++i){
                for(int j = i-1;j>=0;--j){
                    if(arr[i]>arr[j]){
                        dp[i] = Math.max(dp[j]+1,dp[i]);
                        max = Math.max(dp[i],max);
                    }
                }
            }
            System.out.println(max);
        }
    }
}