欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长递增子序列LIS和最长公共子序列LCS

程序员文章站 2022-07-03 18:25:04
...

本文参考了《编程之美》、LeetCode中文题解以及博客
https://blog.csdn.net/George__Yu/article/details/75896330 (LIS)
https://blog.csdn.net/v_july_v/article/details/6695482 (LCS)
https://blog.csdn.net/SongBai1997/article/details/81866559(LCS)
特此感谢!

一、最长递增子序列

问题描述

求一个给定序列最长递增子序列LIS和最长公共子序列LCS中最长的递增子序列的长度。
比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8).

方法一:动态规划

时间复杂度:O(n^2)
思路
状态设计:F[i]代表以A[i]结尾的LIS的长度
状态转移:F[i]=max{F[j]+1}(1<=j< i,A[j]< A[i])
边界处理:F[i]=1(1<=i<=n)

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

const int maxn = 103,INF=0x7F7F7F;
int a[maxn],dp[maxn];

int n,ans = -INF;

int main()
{
    while(scanf("%d",&n) !=EOF)
    {
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            //初始值为1,即以i结尾的LIS子序列长度至少为1
            dp[i] = 1;
        }

        for(int i=1;i<=n;++i)
            for(int j=1;j<i;j++)
            {
    //要求以a[x]结尾的最长递增子序列长度,我们依次比较a[x]与之前所有的a[i](i<x)
                if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
            }

         for(int i=1;i<=n;++i)
            ans = max(ans,dp[i]);

        printf("%d\n",ans);
    }
}

/*
6
1 4 3 2 6 5
*/
方法二:贪心+二分

时间复杂度:O(n^2)
思路
新建一个low数组,low[i]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列,显然其结尾元素越小,越有利于在后面接其他的元素,也就越可能变得更长。
因此,我们只需要维护low数组:
1)追加low数组
对于每一个a[i],如果a[i] > low[当前最长的LIS长度],就把a[i]接到当前最长的LIS后面,即low[++当前最长的LIS长度]=a[i]。
2)更新low数组
对于每一个a[i],如果a[i]能接到LIS后面,就接上去;否则,就用a[i]取更新low数组。
具体方法是:
在low数组中找到第一个大于等于a[i]的元素low[j],用a[i]去更新low[j]。如果从头到尾扫一遍low数组的话,时间复杂度仍是O(n^2)。我们注意到low数组内部一定是单调不降的,所有我们可以二分low数组,找出第一个大于等于a[i]的元素。二分一次low数组的时间复杂度的O(lgn),所以总的时间复杂度是O(nlogn)。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn =300003,INF=0x7f7f7f7f;
int low[maxn],a[maxn];
int n,ans;
int binary_search(int *a,int r,int x)
//二分查找,返回a数组中第一个>=x的位置 
{
    int l=1,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(a[mid]<=x)
            l=mid+1;
        else 
            r=mid-1;
    }
    return l;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]); 
        low[i]=INF;//由于low中存的是最小值,所以low初始化为INF 
    }
    low[1]=a[1]; 
    ans=1;//初始时LIS长度为1 
    for(int i=2;i<=n;i++)
    {
        if(a[i]>=low[ans])//若a[i]>=low[ans],直接把a[i]接到后面 
            low[++ans]=a[i];
        else //否则,找到low中第一个>=a[i]的位置low[j],用a[i]更新low[j] 
            low[binary_search(low,ans,a[i])]=a[i];
    }
    printf("%d\n",ans);//输出答案 
    return 0;
}

二、最长公共子序列

问题描述

求两字符序列的最长公共字符子序列
例如,字符串s1=mzjawxu,s2=xmjyauz,仔细分析下,大体可以看出最长公共子序列是mjau

代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;




//公共子序列(非连续)
int dp[1000][1000];
int LcsNotContinus(string x,string y)
{
    for(int i=0;i<=x.length();i++)
      for(int j=0;j<=y.length();j++)
        if(i==0||j==0)
          dp[i][j]=0;
        else if(x[i-1]==y[j-1])
          dp[i][j]=dp[i-1][j-1]+1;
        else
          dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

    return dp[x.length()][y.length()];
}


//公共子串(连续)
int LcsContinus(string x,string y)
{
    int ans=0;
    for(int i=0;i<=x.length();i++)
      for(int j=0;j<=y.length();j++)
        if(i==0||j==0||x[i-1]!=y[j-1])
          dp[i][j]=0;
        else{
           dp[i][j]=dp[i-1][j-1]+1;
           ans=max(ans,dp[i][j]);
        }
    return ans;
}

int main()
{
    string x = "abcdef";
    string y = "aebfc";
    cout<<LcsNotContinus(x,y)<<endl;  //3
    cout<<LcsContinus(x,y)<<endl;  //1
    return 0;
}

公共子串要求连续,而公共子序列不要求连续,这里参考文章:最长公共子串,使用基本方法、DP、后缀数组等方法解决。

附:

LIS的问题可以通过LCS解决:
最长递增子序列LIS和最长公共子序列LCS

相关标签: LIS LCS