题目描述

blablabla

样例

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

int n;
int a[N],f[N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    int len=0;//len是就是记录最终数组中最长上升子序列的长度
    for(int i=0;i<n;i++)
    {
        int l=0,r=len;//找到从l到len之间小于a[i]的最大值的位置
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(f[mid]<a[i]) l=mid;//如果a[i]的值大于f数组中的最大值 那二分结束后就会将这个值直接赋到数组最后加一位置
            //例如F数组中是 1 4 6  和 a[i]=8 比较 那么二分后r的位置是6的位置 那么a[i] 8的 值就是赋值到f[r+1]的位置 
            //f数组中就会变为 1 4 6 8
            else r=mid-1;
            //如果a[i]的值较小的话
            //例如1 2 4 6  和 5比较的话 二分结束后r的位置是 2 的位置 找到的值是小于a[i]的值的最大值的位置
            //2 是f数组中小于a[i]=5 的值的最大值 然后将f[r+1] 的位置更新为a[i]的值即可 即 1 2 4 6 变为 1 2 5 6 
        }
        len=max(len,r+1);
        f[r+1]=a[i];//将小于a[i]的最大值的位置的后面一位更新成a[i] 
    }
    printf("%d\n",len);//最后len的值就是答案

    return 0;
}