AcWing 896. 最长上升子序列 II（二分优化LIS）

题目连接

https://www.acwing.com/problem/content/description/898/

思路

我们用一个 f [ i ] f[i] f[i]表示以长度为i结尾的子序列的最小值的大小，那么不难发现我们这个f数组是一个单调递增的序列，那么我们就能对我们往前匹配的过程做一个二分优化，也就是找到长度尽量大的且比当前 a [ i ] a[i] a[i]值小的一个位置，如果我们发现当前的这个 a [ i ] a[i] a[i]是比之前所有的元素都要大的，那么我们就应该让我们的最长序列的长度增加，并将 a [ i ] a[i] a[i]放在末尾，表示长度为 l e n len len子序列的末尾最小值，否则的话我们就去更新之前长度的末尾最小值，因为如果一个人比你小还在你后面，那你也没存在的必要了。

代码 代码版本一

#include
using namespace std;

const int N = 1e5+10;
int a[N],n,f[N];

int LIS(){
    f[1] = a[1];
    int len = 1;
    for(int i = 2;i  f[len]) 
            f[++len] = a[i];
        else
            f[lower_bound(f + 1,f+len+1,a[i]) - f] = a[i];
    return len;
}

int main()
{
    
    cin>>n;
    for(int i = 1;i >a[i];
    f[1] = a[1];
    
    cout