$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. 枚举 a[i]，用二分在数组 q 找到小于 a[i] 的最大值的位置，将 a[i] 赋值给这个位置的下一个位置
2. 不能保证数组 q 中的元素就是实际的最长上升子序列，但能保证长度与正确答案一样
3. 例：1，5，8，2；数组 q 中存的是1，2，8；但实际的最长上升子序列是1，5，8；但长度都是 3

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

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

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i];

    int len=0;
    for(int i=0;i<n;i++)
    {
        int l=0,r=len;
        while(l<r) 
        {
            int mid=l+r+1>>1;
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }

        len=max(len,r+1);
        q[r+1]=a[i];
    }

    cout<<len<<endl;

    return 0;
}