最长上升子序列

$O(n^2)$ 算法:

记 $f[i]$ 为以 $a[i]$ 结尾的最长上升子序列长度,

对于每个 $i<j,a[i]<a[j],$ 更新 $f[j]=max(f[j],f[i]+1).$

    for(int i=1;i<=n;i++)f[i]=1;
    for(int j=2;j<=n;j++)
    for(int i=1;i<j;i++)
    if(a[i]<a[j])
    f[j]=max(f[j],f[i]+1);
    for(int i=1;i<=n;i++)
    Ans=max(Ans,f[i]);

$O(nlogn)$ 算法:

记 $f[lon]$ 为当前长度为 $lon$ 结尾的上升子序列的末尾元素中最小的一个.
可以保证 $f$ 序列单调.

从左到右扫一遍, $lon$ 为当前正常上升子序列长度.

对于新的 $j$ ,若 $a[j]>f[lon]$ ,则更新 $f[++lon]=a[j].$

否则二分查找最后一个小于 $a[j]$ 的后一个位置,设为 $k$ ,

则 $f[k]<a[j],a[j]<=f[k+1]$ .则可以将 $f[k+1]$ 替换为 $a[j]$ ,

且替换了一定更优.

    f[1]=a[1];int lon=1;
    for(int i=2;i<=n;i++){
        if(a[i]>f[lon])f[++lon]=a[i];
        else {
            int l=1,r=lon;
            while(l<r){
                int mid=(l+r)>>1;
                if(f[mid]<a[i])l=mid+1;
                else r=mid;
            }
            f[l]=a[i];
        }
    }
    Ans=lon;

最长下降: $<>$ 互换
最长不降/升: $<=$ ， $<$ 互换， $>$ ， $>=$ 互换