最长上升子序列 (LIS) 的两种求法

2017年8月11日

给定 n 个整数 $$A_1,A_2,\\cdots,A_n$$,按从左到右选出尽量多的整数,组成一个上升的子序列.比如,从序列1, 6, 2, 3, 7, 5 中,可以选出上升子序列 1, 2, 3, 5,也可以选出 1, 6, 7,但前者更长.注意,所选出的上升子序列中相邻元素不相等.

有两种办法.

第一种具有 $$O(n^2)$$ 的复杂度.$$dp[i]$$表示以第i个数的最大上升子序列的个数,那么就有 $$dp[i]=\\max(0, d(j)|A_i\\lt A_j, i \\lt j) + 1$$

第二种具有 $$O(n \\log{n})$$的复杂度.

假设已经计算出的两个状态 a 和 b 满足 $$A_a \\lt A_b$$且 $$d(a)=d(b)$$,则对于后续所有状态 i (即 i>a 且 i>b),a并不会比b差——如果 b 满足 $$A_b \\lt A_i $$的条件时,a也满足,且二者的d值相同;但反过来却不一定了,a满足 $$A_a \\lt A_i$$的条件时,b却不一定满足.换句话说,如果我们只保留a,一定不会丢失最优解.

这样,对于相同的d值,只需保留A最小的一个.用 $$g(i)$$表示d值为i的最小状态编号(如果不存在,$$g(i)$$定义为正无穷).根据上述推理可以证明

$$g(1)\\leq g(2) \\leq \\cdots \\leq g(n)$$

g是动态改变的.给定状态i,我们只考虑在i之前已经计算过的状态j(即j<i),上述g序列也是基于这些状态的.随着i的不断增大,要考虑的状态也越来越多,g也随之发生改变.在给定状态i时,可以用二分查找得到满足 $$g(k) \\geq A_i$$的第一个下标k,则 $$d(i)=k$$,此时 $$A_i \\lt g(k)$$,所以更新$$g(k)=A_i$$.

举个例子:求 $$A[5] = [1, 6, 2, 3, 7, 5]$$ 的最长上升子序列.

  1. 将A[0]放入G[],得 G[0] = {1}
  2. 将A[1]放入G[],得 G[0, 1] = {1, 6},这里由于A[1]比第一步的 G[] 中最大的一个元素还要大,所以加到 G[] 的末尾.
  3. 将A[2]放入G[],得 G[0, 1] = {1, 2},这里由于2小于6,所以把6改为2
  4. 将A[3]放入G[],得 G[0, 1, 2] = {1, 2, 3},这里由于A[3]比第3步的 G[] 中最大的一个元素还要大,所以加到G[]的末尾.
  5. 将A[4]放入G[],得 G[0, 1, 2, 3] = {1, 2, 3, 7}
  6. 将A[5]放入G[],得 G[0, 1, 2, 3] = {1, 2, 3, 5}

所以,最后最长公共子序列的个数也就是 G[] 中元素的个数.通常用二分查找来查找 A[i] 在 G[] 中的位置,因此算法时间复杂度 $$O(n\\log{n})$$

for (int i = 1; i <= n; i++)
    g[i] = INF;
for (int i = 0; i < n; i++) {
    int k = lower_bound(G + 1, G + n + 1,  A[i]) - G;
    d[i] = k;
    G[k] = A[i];
}

题目链接:http://poj.org/problem?id=2533

第一种方法的代码:

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1005;
int a[N], dp[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    int ans = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

第二种方法的代码:

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
int a[N], g[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    int ans = 0;
    memset(g, INF, sizeof(g));
    for (int i = 0; i < n; i++) {
        int k = lower_bound(g, g + n, a[i]) - g;
        g[k] = a[i];
        ans = max(ans, k + 1);
    }
    printf("%d\n", ans);
    return 0;
}
去打赏

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注