java 代码

import java.io.*;
import java.lang.*;

class Main{

    static int n = 0, N = 100010;
    static int[] a = new int[N], st = new int[N];
    static int hh = 0;

    static int binserySearch(int num, int[] nn){//找到从右到左第一个大于num的数
        int l = 1;
        int r = hh;
        while(l < r){
            int mid = l + r >> 1;
            if(nn[mid] >= num)r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args)throws Exception{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(buf.readLine());
        String[] nums = buf.readLine().split(" ");
        for(int i = 1; i <= n; ++i){
            a[i] = Integer.valueOf(nums[i - 1]);
            int index = binserySearch(a[i], st);//找到大于a[i]的下标
            if(hh == 0 || st[hh] < a[i]){//栈空或者栈不存在这个数并且栈顶元素大于该数
                st[++hh] = a[i];//更新长度
            }else if(st[index] > a[i]){//更新序列最小值
                st[index] = a[i];
            }
        }
        System.out.print(hh);
    }
}