题目描述

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

算法：二分

时间复杂度：$O(nlogn)$

• 我们已经知道这题要是用第一种算法暴力的话，肯定超时的，所以要优化算法。

• 比如一个数列是2 1 5 6 9,我们要是f[3]的话要从a[1]枚举到a[2]，但你会发现肯定是选1更有利，这其实是贪心的思，所以我们要一个数组记录不同长度下最后一个数的最小值是多少，比如长度为1时，q[1]=1。根据y总的算法基础课知（建议大家购买，hh）：q是一个严格递增的数列，所以可以用二分找出最长的的并且最后一个数小于a[i]，这样才能把a[i]接到上面；

#include <iostream>
const int N=100006;
int a[N],q[N],l,r,n,mid,len;//a数组记录每一个数，q数组记录不同下长度最后一个数最小是什么
using namespace std;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    len=0;//初始化，因为长度一开始只能是0
    for(int i=1;i<=n;i++)
    {
        l=0,r=len;为什么l=0呢？因为r要等于len，而len长度默认为0，为了防止l==r所以l=0
        while(l<r)
        {
            mid=(l+r+1)>>1;//因为l=mid,所以要+1
            if(q[mid]<a[i])//必须是小于，等于的话也是不能拼接在一起的；
            {
                l=mid;//不能是mid+1，如果q[mid]<a[i]，呢么q[mid+1]不一定也小于a[i]，可能等于
            }
            else
            r=mid-1;//不是r=mid,因为q[mid]一定>=a[i]，不能接在一起
        }
        q[l+1]=a[i];//q[l+1]一定是大于等于a[i]
        if(l==len)//呢么长度要+1，因为已经把a[i]接上去了
        len++;
    }

    cout<<len;
}
blablabla