目录
  1. 方法一:最长公共子序列法
  2. 方法二:动态规划法(O(N^2))
  3. 方法三:O(NlogN)算法
最长递增子序列(LIS)的三种算法

最长递增子序列:给定一个长度为N的数组,找出一个最长的单调递增子序列,子序列不一定连续,但初始顺序不能乱。
比如数组A={1,3,4,2,5},其最长递增子序列为1,3,4,5




方法一:最长公共子序列法

对于给定长度为N的数组A:

  1. 使数组B为排序后的数组A (O(NlogN))
  2. 求出A与B的最长公共子序列(LCS) (O(N^2))
    1. 对求得的公共子序列进行去重 (O(N))

例如:A = {1,3,5,4,4,6}
则B = {1,3,4,4,5,6}
最长公共子串C = {1,3,4,4,6}
对C去重得到结果:{1,3,4,6}

方法二:动态规划法(O(N^2))

  • 状态$dp[i]$:以第i个数结尾的最长递增子序列的长度
  • 状态方程:$dp[i] = dp[j]+1$ 其中 $a[j] < a[i],j < i$且 $dp[j]$ 最大。若没有满足的a[j]则$dp[i]=1$
  • 最后max(dp)即为最长递增子序列的长度
  • 若要求得最长递增子序列,可以用另外的数组lastidx记录上述的“j”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;

int main()
{
int a[6] = {1,3,5,4,4,6};
int dp[6],lastidx[6];
for(int i = 0;i < 6;i++)
{
dp[i] = 1; lastidx[i] = i;
for(int j = 0;j < i;j++)
{
if(a[j] < a[i] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
lastidx[i] = j;
}
}
}
int maxx = 0, maxi = 0;
for(int i = 0;i < 6;i++)
if(dp[i]>maxx)
{
maxx = dp[i];
maxi = i;
}
int lis[6];
for(int i=maxx-1;i>0;i--)
{
lis[i] = a[maxi];
maxi = lastidx[maxi];
}
cout << "最长公共子串长度:" << maxx << endl;
for(int i=0;i<maxx;i++)
cout << lis[i] << " ";
return 0;
}

输出结果为:

最长公共子串长度:4
1 3 5 6

方法三:O(NlogN)算法

对于给定长度N的数组a,声明数组last[N],last[i]的意义为:长度为i的递增子序列的最后一个数字,在循环数组a时更新这个数组。

比如{1,3,5,4,4,8,6,7}

a[0] = 1, 则长度为1的LIS为1,则last[1] = 1 , len = 1;

a[1] = 3, 3大于此前的最后一位1,故目前的最长的LIS可以为2了,故last[2] = 3, len = 2;

a[2] = 5, 同理,last[3] = 5 , len = 3;

a[3] = 4, 其可以加在5和3之间,所以可以把5替换掉,即last[3] = 4;

a[4] = 4,与last[3]相等了,所以不做变动。

a[5] = 8,比最后一位(5)大,所以last[4] = 8, len = 4;

a[6] = 6,在5和8中间,所以last[4] = 6;

a[7] = 7, 比最后一位6大,所以last[5] = 7, len =5;

最终得到结果LIS长度为:5,last数组为:1,3,4,6,7

注意last数组并不一定是LIS,而是对应长度的LIS的最后一位。</font>
而注意到last数组往往是有序的,所以数组元素只有替换而没有挪动,故每次插入只要用二分查找即可。因此复杂度为O(N logN)

  • 若想得到最长递增子序列,同样可以使用数组lastidx和pre,用来标识至此为止该长度的LIS的最后一个数的下标和当前数字的来源
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define maxn 8

    int main()
    {
    int a[maxn] = {1,3,5,4,4,8,6,7};
    int last[maxn], lastidx[maxn], pre[maxn], len=0, maxi;
    memset(last,0x3f,sizeof last);
    last[0] = -inf;
    for(int i=0;i<maxn;i++)
    {
    int pos = lower_bound(last, last+maxn, a[i])-last; //二分查找
    last[pos] = a[i];
    lastidx[pos] = i; //该长度的LIS的最后一个数的下标
    pre[i] = lastidx[pos-1]; //当前数字的来源(LIS中的前一位,即lastidx[长度-1])
    if(pos >= len)
    {
    len = pos;
    maxi = i; //LIS最后一个数字的下标
    }
    }
    int lis[maxn];
    cout << "最长公共子串长度:" << len << endl;
    for(int i=len-1;i>=0;i--)
    {
    lis[i] = a[maxi];
    maxi = pre[maxi];
    }
    for(int i=0;i<len;i++)
    cout << lis[i] << " ";
    return 0;
    }

输出:

最长公共子串长度:5
1 3 4 6 7

文章作者: Irimsky
文章链接: /2019/08/16/最长递增子序列(LIS)的三种算法/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Irimsky's Blog

评论