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

题目描述

给定一个长度为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构成的子序列235最长)

题解

这个问题就是著名的最长上升子序列(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);
}
请博主喝杯咖啡~
0%