最长上升子序列（LIS）详解

最长上升子序列（Longest Increasing Subsequence）解法和优化

学习动态规划的入门知识碰到的经典问题，这里记录一些我的理解

最长上升子序列（LIS）

两个概念

首先，需要明确两个概念：

  1. 子串（Substring）：对应字符串从左到右的顺序摘取的片段，要求必须连续（不能有间隔字符），如：$abcde$种$bcd$就是一个子串；

  2. 子序列（Subsequence）：对应字符串从左到右的顺序摘取片段，要求可以有间隔字符，如：$abcde$中$ace$是一个子序列。

因此，一定有如下说法：子串一定是子序列，而子序列不一定是子串，这很好理解。

问题描述

给定一个长为n的数列，求出这个数列的最长上升子序列的长度。

Sample Input:

1
2
5
4 2 3 1 5

Sample Output:

1
3

数据范围：$1\leq n\leq 1000; 0\leq a_i \leq 1e6$

一般解法

具体思路：

  1. 定义状态： $dp[i]$表示以$a_i$为末尾的最长上升子序列的长度；

  2. 状态转移： 一种是$dp[i]$本身，另一种则是在遍历过程中出现的以$a_j(a_j<a_i且j<i)$为结尾的LIS末尾加上$a_i$得到的子序列；

  3. 方程如下：

    时间复杂度$O(n^2)$，可以开始搞了。

AC代码($O(n^2)$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

int dp[100005],a[100005];
int len,n;
int ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			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]);
	}
	cout<<ans<<endl;
	return 0;
}

优化

上述方法看起来很巧妙，并且感觉已经足够完美了，那么能不能再完美一些（时间复杂度再低一些）呢？

答案是可以。

  • 我们定义一个新的状态：$dp[i]$表示所有数组成的LIS中，所有长度为$i$的LIS中的末尾元素最小值（orz真的很难理解）；

  • 状态定义好了，我们需要做的就是遍历一遍$a_1$到$a_n$，并更新这个$dp$数组，具体操作如下：

    1. 首先，$dp$数组的长度为0，我命名为len=0；

    2. 出现$a_i>dp[len]$时，不管三七二十一，直接加在$dp[len]$后面，并使得len++；

    3. 出现$a_i<dp[len]$时，我们需要把这个$a_i$替换掉$dp$数组从左到右第一个大于等于$a_i$的元素（注意：此时dp数组长度不变），因为我们要求最优，因而就需要$dp$数组里面元素尽可能小，这样才有更大的可能性再去往后加数。

具体思路是这样，是不是一脸懵逼？

没事，我们来手动模拟一下：

以数组（4，2，3，1，5）为例：

首先，len = 0，dp = ｛0，0，0，0，0｝，

开始：

指向第一个元素，4 > 0，因此加进dp里，dp = ｛4，0，0，0，0｝len = 1；

指向第二个元素，2 < 4，因此替换掉4，dp = ｛2，0，0，0，0｝len = 1；

指向第三个元素，3 > 2，因此加进dp里，dp = ｛2，3，0，0，0｝len = 2；

指向第四个元素，1 > 3，因此替换掉2，dp = ｛1，3，0，0，0｝len=2；

指向第五个元素，5 > 3，因此加进dp里，dp = ｛1，3，5，0，0｝len = 3;

结束。

因此 len= 3

这样好理解多了吧？

但是我们可以发现，最后的dp数组它不是正确的答案（正确答案是2，3，5），但这并不影响len长度的真确性，为什么呢？因为我们在操作$a_i<dp[len]$的时候，只是把更优的数（更小的数）替换掉了第一个比他大的数，而长度并没有改变，这种求最优的过程并没有影响到LIS的长度，而这个dp数组则代表了一种最可能性，代表每一步都是最优的，意思是如果后面还有数的话，这个答案就可以再接着往下更新，可能又有新的替换。（这里可能表述得不太清晰，还是需要自己多悟呀）

可有人会问了：这确实是个新思路，但遍历一遍a数组需要n复杂度，插入到dp也需要n复杂度，这不还是$O(n^2)$复杂度吗？

话是这么说，但我们的插入操作可以利用二分查找（lower_bound或者你手打）来优化呀！

为什么可以呢？答：因为dp数组一定是单调的（依据状态转移过程不难得出）。

AC代码（$O(nlogn)$）

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
38
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf = 1<<30;

ll f[100005],a[100005];
ll n;
ll len;

//int bound(int x){
//	int l=1,r=len;
//	while(l<r){
//		int mid = (l+r)>>1;
//		if(f[mid]>x){
//			r=mid;
//		}else l=mid+1;
//	}
//	return l;
//}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		if(f[len]<a[i]){
			f[++len] = a[i];
		}else{
			int pos = lower_bound(f+1,f+len+1,a[i])-f;
			f[pos] = a[i];
		}
		//cout<<len<<" ";
	}
	cout<<len<<endl;
	return 0;
}
  • 第一次学这个东西可能确实需要点时间来理解，我会努力加深印象的。
    以上。