最长上升子序列(LIS)问题

(iBus的输入法真的难用啊。。。用起来的感觉就像被电脑和键盘cj/(ㄒoㄒ)/~~,写到一半忍不住去换了fcitx+搜狗,然而可能是我的使用姿势不对,总出BUG,不过现在终于对上号了owo~)

 

这个问题让我想了N久N久N久,深深地感到智商欠费怀疑人生,我真是应该自挂东南枝。。


      问题:给出一个序列 例如(2 1 5 3 6 4 8 9 7),求该序列的最长上升子序列长度(1 3 4 8 9,长度为5)。

最长上升子序列问题,常用解法有两种,都用到了动态规划的思想,一种是直接用动态规划,比较好想,但是算法复杂度为O(n^2),另一种算法进行了优化,把时间复杂度降低到了O(nlogn),此两种方法本文都进行讲解,先看第一种

  • 通称O(n^2)算法

         设a为存储序列的数组,设f[i]为以i结尾最长子序列的长度,那么如何递推出f[i]的值呢?我们设一个变量j来表示,1<=j<=i-1,对于所有的a[j],只有当a[j]<a[i]的时候,我们才需要判断是否需要把a[i]添加到f[j]中,当然我们需要注意,f[i]的以i结尾的最长子序列的长度,所以我们要在所有可以添加a[i]的子序列中,找到最长的那个子序列,然后我们把a[i]添加进子序列中,另f[i]=f[j]+1即可。

         我在某篇博客上看到了f[i]=max(f[j](0<=j<i))+(a[i]>a[j]?1:0) 这样的公式,仔细研究这个公式其实是有BUG的,因为他找到的子序列max(dp[j])不一定能满足a[i]可以被添加进去,这点要注意仔细思考,不然很容易就出错。

         正确的推理公式应该是:f[i]=max( f[j] | (1<=j<=i-1,a[i]>a[j]) ) + 1

         我觉得这个算法是达不到O(n^2)的复杂度的。

代码:

int lis1(int a[],int n)
{
    int *f=new int[n+1];
    for(int i=0;i<=n;i++){f[i]=0;}//初始化
    int Max;
    for (int i = 1; i <= n; ++i){
        Max = 0;
        for (int j = 1; j <= i-1; ++j){
            if (a[i] > a[j]){
                Max = max(Max, f[j]);//找到可以把a[i]作为结尾的最长子序列
            }
        }
        f[i] = Max + 1;//把a[i]加入到这个子序列中
    }
    Max = 0;
    for (int i = 1; i <= n; ++i){//找到最长上升子序列
        if (f[i] > Max)    Max = f[i];
    }
    return Max;
}
  • O(nlogn算法)

         分析上面的算法发现,每次都要从i-1个数里面遍历,再找到最长的子序列,这就提高了计算时间,那么如何优化呢?是否有一种办法把这个寻找的过程简化?

        我们使用b[i]来记录长度为i的上升子序列的末尾元素的最低值 ,这是什么意思?长度为i的子序列可能有很多个,而我们为了寻找整个序列的最长上升序列,只需要关注长度为i的序列末尾元素的最低值,因为末尾元素的值越低,我们越可能得到更长的上升子序列,这是一种贪心算法的思想,显然b数组的递增的。用反证法简单地证明一下,假若存在i<j,b[i]=a,b[j]=b,且a>b,那么长度为j的上升序列里面一定包含一个长度为i的子上升序列,且b[i]<b[j],与假设矛盾。

         我们假设b最开始是没有长度的,通过依次读取每一个a[i]来更新b的长度以及b数组中存储的值。

         当我们读取到的a[i] 大于当前最长子序列的末尾元素最低值,那么a[i]可以被加入到这个子序列中,我们把当前最长子序列长度+1,并且更新b数组的值。

         如果条件不成立,那么我们无法添加a[i]到当前最长的子序列中,这时候我们用a[i]更新长度不是最长的子序列末尾元素的最低值,如何更新呢,我们在b数组中从前向后找到 第一个大于a[i]的数,然后用a[i]去更新这个值,这是什么诡异操作?假如b[1-5]=1 3 4 6 9,a[i]=5,那么a[i]可以加入的子序列就只有b[1-3]=1 3 4,不过我们既然要求最长子序列,那就让a[i]并入长度为3的子序列,并入后长度为4,这时我们要更新b[4]的值,忘记b存储的是什么了嘛?是长度为i的上升子序列的末尾元素的最低值,a[i]是小于原来的b[4]的,所以把a[i]并入长度为3的子序列之后及时用a[i]更新b[4]的值。

         如果对这里的操作还不是很明白的话,可以自己模拟一遍,在纸上写一写画一画~也可以点击这个链接:https://www.felix021.com/blog/read.php?1587 ,看一遍他的模拟过程。

下面放代码:

int lis2(int a[],int n){
    int ans=0;//假设b最开始的长度为0
    int *b=new int[n+1];
    for(int i=0;i<=n;i++){b[i]=0;}//初始化b的值
    for(int i=1;i<=n;i++){//依次读取a[i]的值并更新数组b
        if(b[ans]<a[i]){//如果可以被添加到长度为ans的子序列里面
            b[++ans]=a[i];//添加并且ans++;
            continue;
        }else{
            b[insert_x(b,ans,a[i])]=a[i];//否则就使用a[i]更新b数组的值
        }
    }
    delete []b;
    return ans;//最后数组的长度ans就是答案。
}
int insert_x(int b[],int n,int x){//寻找插入点,插入第一个大于x的位置,b是数组,查找范围是[0,n]
    int mid=0;
    int front=0;
    int rear=n;
    while(front!=rear-1){//使用二分查找
        mid=(front+rear)/2;
        if(x>b[mid]){
            front=mid;
        }else{
            rear=mid;
        }
    }
    return front+1;
}

注意这个算法为什么比第一个算法快,因为b是递增的数列,所以查找插入点的时候可以使用二分查找,二分查找的速度远远快于遍历整个数组,所以,这就体现了数据结构对算法的重要程度。

下面贴一个完整可以运行的代码:

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int lis1(int a[],int n);
int lis2(int a[],int n);
int insert_x(int b[],int n,int x);//在前N个数据里面,返回应该插入的位置
int main(){
    int n=0;
    cin>>n;
    int *a=new int[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<lis1(a,n)<<endl;
    cout<<lis2(a,n)<<endl;
    delete []a;
    return 0;
}
int lis1(int a[],int n)
{
    int *f=new int[n+1];
    for(int i=0;i<=n;i++){f[i]=0;}//初始化
    int Max;
    for (int i = 1; i <= n; ++i){
        Max = 0;
        for (int j = 1; j <= i-1; ++j){
            if (a[i] > a[j]){
                Max = max(Max, f[j]);//找到可以把a[i]作为结尾的最长子序列
            }
        }
        f[i] = Max + 1;//把a[i]加入到这个子序列中
    }
    Max = 0;
    for (int i = 1; i <= n; ++i){//找到最长上升子序列
        if (f[i] > Max)    Max = f[i];
    }
    return Max;
}
int lis2(int a[],int n){
    int ans=0;
    int *b=new int[n+1];
    for(int i=0;i<=n;i++){b[i]=0;}
    for(int i=1;i<=n;i++){
        if(b[ans]<a[i]){
            b[++ans]=a[i];
            continue;
        }else{
            b[insert_x(b,ans,a[i])]=a[i];
        }
    }
    delete []b;
    return ans;
}
int insert_x(int b[],int n,int x){
    int mid=0;
    int front=0;
    int rear=n;
    while(front!=rear-1){
        mid=(front+rear)/2;
        if(x>b[mid]){
            front=mid;
        }else{
            rear=mid;
        }
    }
    return front+1;
}

输入:第一行输入一个数字N,后面输入N个数字,使用tab、空格、回车进行间隔

输出:使用两个算法进行计算的最长上升子序列长度

样例:

    输入:

         9
         2 1 5 3 6 4 8 9 7

    输出:

         5

         5

 

发表评论

邮箱地址不会被公开。