题目描述

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数N。

第二行包含N个整数，表示完整序列。
输入格式
第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，
−109≤数列中的数≤109

样例

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

问题

1. 首先明白 q[]数组的意义是啥？
2. 如何维护q数组
3. 时间复杂度如何优化的？

分析

1. q[]数组 是一个队列，表示的是最终存储的最长子序列；
2. 最终的长度 就是q的长度；
3. 维护q数组，遍历每一个a[i]；看下a[i]应该插入到 q中的哪个位置？如果说 要插的q数组的中间，那说明 没有必要了，不会更新 最长子序列；
4. 如果是 在q中找不到 a[i] 那么将其加入到 队尾，并且更新队列的长度；
5. 如果是q的队尾是a[i]；那么此时 更新不更新 都无所谓；
6. 查找 使用二分查找的方式

参考代码

import java.util.*;
public class Main{
    static int N=100010;
    static int []a=new int [N];
    //q 单调栈用来存储 最终的保存结果； 
    static int []q=new int [N];
    static int len;
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }

        for(int i=1;i<=n;i++){
            //使用二分查找在 已经保存的结果中来找a[i]
            int l=0;int r=len;
            while(l<r){
                int mid=l+r+1>>1;
                if(q[mid]<a[i]){
                    l=mid;
                }else{
                    r=mid-1;
                }
            }
            //如果该点在队尾 或者不在队列中  那就代表可以加入到队列；如果是队尾，就不更新了长度，
            //可以将a[i]加到队尾，那么就将其加到队尾 并更新len的长度；
            len=Math.max(len,l+1);
            //将此数加到队尾；
            q[l+1]=a[i];
        }
        // System.out.println(Arrays.toString(q));
        System.out.println(len);
    }
}