LIS(Largest Increase Sequence)

如果这个题用暴力动态规划那么会超时因为时间要求是1s，cpp能执行的操作大概是10^7-10^8之间。用java更不行了。用上题的做法时间复杂度是n^2级别，大概是10^5*10^5=10^10，一定过不去。

方法：贪心

维护一个low数组（里面存放的是最长连续递增子序列中每个长度最后一个元素的最小值。每个元素都代表着一类情况，所以也划分到dp上来了。），又因为low数组中既然存放是每个长度的连续递增子序列最后一位的最小值，那么一定是单调递增的，这是显然的，当然可以用反证法证明。所以在low中寻找元素可以用二分。

时间复杂度

时间复杂度是o(nlogn). 10^5log10^5 大约是10^6 一定可以通过。

import java.util.*;
public class Main{
    static int[] low;
    static int[] arr;
    static int idx=0;
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        low=new int[n+1];
        low[0]=-0x3f3f3f3f;//保证每次查找都可以找到。
        arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
            insert(arr[i]);
        }
        System.out.println(idx);
    }
    public static void insert(int i){
        int l=0,r=idx;
        while(l<r){
            int mid=l+r+1>>1;
            if(low[mid]<i) l=mid;
            else r=mid-1;
        }
        low[l+1]=i;
        if(l+1>idx) idx++;
    }
}