LIS最长上升子序列O(n^2)与O(nlogn)的算法

动态规划

最长上升子序列问题（LIS）。给定n个整数，按从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0个或多个数，其他数的顺序不变）。例如序列1, 6, 2, 3, 7, 5，可以选出上升子序列1, 2, 3, 5，也可以选出1, 6, 7，但前者更长。选出的上升子序列中相邻元素不能相等。

最容易想到的办法就是用一个数组f[i]保存到达第i个数的LIS

初始化f[i]=1

更新 f[i]=max{f[j]+1,f[i]|a[j]<a[i],1<=j<i}

即在第i位置前的比i小的最大的LIS+1

时间复杂度O(n^2)

#include<cstdio>

#include<iostream>//vj1098

#define ll long long

#define _max(a,b) ((a)>(b)?(a):(b))

using namespace std;

const int N=;

int n,a[N],ans;

int f[N],g[N];

int main()

{

    freopen("sample.in","r",stdin);

    cin>>n;

    for(int i=;i<=n;i++)

    scanf("%d",&a[i]),f[i]=g[i]=;

    for(int i=;i<=n;i++)

     for(int j=;j<i;j++)

      if(a[j]<a[i])

       f[i]=_max(f[i],f[j]+);

    for(int i=n;i>=;i--)

     for(int j=n;j>i;j--)

      if(a[j]<a[i])

       g[i]=_max(g[i],g[j]+);

    for(int i=;i<=n;i++)

    ans=_max(ans,f[i]+g[i]-);

    cout<<n-ans;

    return ;

}

从蓝书和网上学到了一种更高效的O(nlogn)的算法

大概思路如下

　　d[i]表示以i结尾的最长的LIS的长度，则d[i]=max{0,d[j]|j<i,Aj<Ai}+1,最终答案是max{d[i]}。如果LIS中的元素可以相等，把小于号改成小于等于号即可。

　　假如已经计算出两个状态a，b满足Aa<Ab,且d[a]=d[b],则对于后续所有状态i（即i>a且i>b）来说，a并不会比b差——如果b满足Ab<Aa的条件，a也满足。换句话说，如果我们只保留a，一定不会丢失最优解。

　　这样，对于相同的d值，最需要保留A最小的一个。我们用g[i]表示d值为i的最小状态编号（如果不存在，g[i]定义为正无穷）。根据上推理可证明

　　g[1]<=g[2]<=g[3]<=……<=g[n]

#include<cstdio>

#include<iostream>

#define ll long long

#define _max(a,b) ((a)>(b)?(a):(b))

using namespace std;

const int N=;

int n,k,a[N],b[N],o[N],ans,ma,mb;

int j,da[N],db[N],len,la,lb,mid;

int findpos(int *d,int l,int r,int key){

    while(l<=r){

        mid=(l+r)>>;

        if(key>d[mid]){

            if(key<=d[mid+])

                return mid;

            else l=mid+;

        }else r=mid-;

    }return ;

}

int main(){

    cin>>n>>k;

    for(int i=;i<=n;i++)    scanf("%d",o+i);

    for(int i=;i<k;i++)    o[i]<o[k]?a[++la]=o[i]:la=la;

    for(int i=k+;i<=n;i++)    o[i]>o[k]?b[++lb]=o[i]:lb=lb;

    da[]=a[],len=,j=;

    for(int i=;i<=la;i++)da[a[i]>da[len]?++len:findpos(da,,len,a[i])+]=a[i];

    db[]=b[],len=,j=;

    for(int i=;i<=lb;i++)db[b[i]>db[len]?++len:findpos(db,,len,b[i])+]=b[i];

    for(int i=la;i>=;i--)da[i]?ans+=i,i=:i=i;

    for(int i=lb;i>=;i--)db[i]?ans+=i,i=:i=i;

    cout<<ans+;

    return ;

}

汝佳的code核心

for(int i=;i<=n;i++)g[i]=INF;

for(int i=;i<=n;i++){

    int k=lower_bound(g+,g+n+,A[i])-g;

    d[i]=k;

    g[k]=a[i];

}

LIS最长上升子序列O(n^2)与O(nlogn)的算法的相关教程结束。