题目描述

896.最长上升序列
这道题与895一样的题 只是这道题数组n达到了1e5我们需要用时间复杂度更加少的方法，我们可以用a数组存当前数组，用f数组存储我们最长的上升子序列，因为是递增的我们就能用到二分来维护我们的上升序列，先将a[1]存到f[1]中此时cnt=1；循环每个a[i]到a[n]每次都要与我们的上升序列最大的数f[cnt]相比，如果比它大就直接加入到f数组中f[++cnt]=a[i]，如果比他小就要我们经过一次二分找到比数组中第一次比它大的下表，我们可以 t = find(a[i]) 找到下标后我们就可以f[t] = a[i] 就将我们循环到当前的数给到这个位置，二分判断l=1；r=cnt；if(f[mid]>=x);这样循环至所有数组a我们就可以输出cnt的值就是我们的答案

样例

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N= 1e5+10;
int f[N], a[N];
int n,cnt;

int find(int x)
{
    int l=1,r=cnt;
    while(l<r)
    {
        int mid =(l+r)/2;
        if(f[mid]>=x) r=mid;
        else          l=mid+1;
    }

    return l;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int t;
    f[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>f[cnt]) f[++cnt] =a[i]; 
        else
        {
            t=find(a[i]);
            f[t] =a[i];
        }
    }
    cout<<cnt<<endl; 
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla