算法详解：最长上升子序列

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 516 阅读时长 ≈ 2 分钟

题目描述

给定一个长度为n的数列a0, a1, a2...an-1，求出这个序列中的最长的上升子序列的长度，上升子序列的定义为：对于任意的i<j，都满足ai<aj。

限制条件：1≤n≤1000，0≤a≤1000000

样例：

输入：

1
2
n = 5
a = {4, 2, 3, 1, 5}

输出：

1
3（a1, a2, a4构成的子序列2，3，5最长）

题解

这个问题就是著名的最长上升子序列（LIS，Longest Increasing Subsequence）问题，这个问题有两种解法，第一种解法是O(n²)的DP解法，第二种解法是O(nlogn)的DP加二分解法。

O(n²)算法

首先我们可以来建立一下DP的递推关系：

1
定义dp[i]:=以ai为末尾的最长上升子序列的长度

以ai结尾的上升子序列是：

1
2
只包含ai的子序列
在满足j<i并且aj<ai的以aj为结尾的上升子列末尾，追加上ai后得到的子序列

这二者之一。这样就能得到如下的递推关系：

1
dp[i]=max{1, dp[j]+1|j<i且aj<ai}

使用这个递推公式可以在O(n²)时间内解决这个问题。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 输入
int n;
int a[MAX_N];

int dp[MAX_N];

void solve() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    printf("%d\n", res);
}

这个方法比较简单，但是时间复杂度也比较高。下面我们来看看更优的解法。

O(nlogn)

之前我们的思路是求出以第i个元素为结尾的最长上升子序列长度，我们可以换个思路，考虑一下dp[i]为最长上升子序列长度为i情况下最小的元素，这样我们就可以通过二分来进行优化，代码如下：

1
2
3
4
5
6
7
8
9
int dp[MAX_N];

void solve() {
    fill(dp, dp+n, INF);
    for (int i = 0; i < n; i++) {
        *lower_bound(dp, dp + n, a[i]) = a[i];
    }
    printf("%d\n", lower_bound(dp, dp + n, INF) - dp);
}