一.LIS

题目传送门
给定一个长为 \(n\) 的序列 \(a_i\)，求这个序列的最长单调上升子序列长度。
\(1\)≤\(a_i\)≤\(n\)≤\(10^5\)

二.解析

\(n^2\)解法在此不再赘述，显然此方法过不了此题，下面考虑\(nlogn\)解法即二分
定义\(f[n]\)为长度为\(n\)的子序列的最后一项的数值,\(len\)为当前的最优解，不难发现\(f[n]\)是单调递增的
对于当前处理的元素\(a[i]\)，分为两种情况
1.\(a[i]>f[len]\),此时自然可以直接将\(a[i]\)接在\(len+1\)处，且更新\(f[len+1]\),即\(f[++len]=a[i];\)
2.\(a[i]<=f[len]\),此时无法形成\(len+1\)长的上升子序列，但我们要考虑将短于\(len\)的之前存储过的上升子序列的末项变得更小，这样才更有机会以后向这个序列后接入更多的数。\(f[n]\)是单调的，考虑二分，找到最小的\(f[k]>=a[i]\)用\(a[i]\)更新\(f[k]\)。就是找到一个\(f[k]\)，我们可以想象它所代表的一串上升子序列，将末项改小后，仍然使此上升子序列合法。其实，\(f[k]\)都是由\(f[k-1]\)继承而来的，所以\(f[k-1]\)即我们想象里的长度为k的上升子序列的倒数第二项，所以只要将\(a[i]>f[k-1]\)同时\(a[i]<=f[k]\)修改就一定合法。又因为当\(f[k]\)较小时，我们会发现这总归不如修改\(f[b] (b>k)\)来的好，因为末项修改后大家都一样，即以后能装下更多数的潜力是一样的，那么就是当前长度越长越优，并且在以后的使上升子序列变长的过程中，是从最优方案为基础的，不是最优的那些方案也不必修改了。受此二者限制，我们只需找到最小的\(f[k]>=a[i]\)并加以修改即可。此处建议读者手动模拟，深刻理解。

三.AC代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,a[100001],f[100001],dp[100001];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=0x7fffffff;
    }
    f[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        int l=0,r=len,mid;
        if(a[i]>f[len])f[++len]=a[i];
        else 
        {
        while(l<r)
        {   
            mid=(l+r)/2;
            if(f[mid]>=a[i])r=mid;
            else l=mid+1; 
        }
        f[l]=min(a[i],f[l]);
        }
    }
    cout<<len<<endl;
	return 0;
}