题解 | #Redraiment的走法#

import java.util.Scanner;
import java.util.Arrays;
import java.io.InputStream;
import java.io.PrintStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) {
        InputStream inps=System.in;
        Scanner in = new Scanner(inps);

        String temp=in.nextLine();
        int n=Integer.parseInt(temp);
        temp=in.nextLine();
        try{
            inps.close();
        }catch(IOException e){
            e.printStackTrace();
        }
        in.close();

        String arr[]=temp.split(" ");
        int height[]=new int[n];
        int i=0;
        for(;i<n;++i){
            height[i]=Integer.parseInt(arr[i]);
        }
        
        i=maxStep(height,n);
        PrintStream pt=System.out;
        pt.println(i);
        pt.close();
        
    }
    public static int maxStep(int arr[],int n){
        int i=0;
        int j=0;
        int a[]=new int[n];
        int len[]=new int[n];
        int index=0;
        a[j++]=arr[0];
        len[0]=1;
        for(i=1;i<n;++i){
            if(arr[i]>a[j-1]){
                a[j++]=arr[i];
                len[i]=j;
            }else{
                index=Arrays.binarySearch(a,0,j,arr[i]);
                if(index<0){
                    index=-index-1;
                    a[index]=arr[i];
                }
                len[i]=index+1;
            }
        }

        return j;
    }
}