最长上升子序列LIS,最经典的单串线性DP状态设计

  |  

摘要: 最长上升子序列,动态规划,二分

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一下只要学动态规划就必然涉及的一题:最长上升子序列。它代表了单串上最经典的一类状态设计思路和阶段划分。此外 LIS 问题还有一个很有技巧性的二分算法。

最长上升子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

提示:

1
2
1 <= nums.length <= 2500
-1e4 <= nums[i] <= 1e4

示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1

进阶:

你能将算法的时间复杂度降低到 $O(n \log(n))$ 吗?

算法1:动态规划

LIS 是单串线性 DP 的基础问题,它的状态表示是 $dp[i]$,含义是以 $i$ 结尾的最长上升子序列长度。

阶段划分为子序列的结尾位置。阶段已经可以表示状态,因此状态中没有附加信息维度。

LIS 的这种状态表示和阶段划分方法在单串线性 DP 问题中很常见,完整算法如下:

1
2
3
4
5
6
7
8
9
10
11
dp[i] := [0..i] 上以 i 结尾的最长上升子序列长度

初始化
dp[i] = 1

答案
max(dp[i])

转移
dp[i] = 1 + max(dp[j])
0 <= j < i, nums[j] < nums[i]

$O(N^{2})$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
vector<int> dp(n, 1);
int result = 0;
for(int i = 0; i <= n - 1; ++i)
{
for(int j = 0; j <= i - 1; ++j)
{
if(nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
}
result = max(result, dp[i]);
}
return result;
}
};

类似于以下的状态转移方程可以用权值线段树或权值树状数组优化,参考文章 权值树状数组优化DP

LIS

算法2:二分

若 nums 的长度为 $n$,那么最长上升子序列(LIS)的长度是有范围的,最小可能是 1,也就是整个数组是单调不增的,例如下面这个 $n = 5$ 数组,LIS 只能取到 1 的长度。

1
nums1 = [4, 3, 3, 2, 1]

最长可能是 $n$,也就是整个数组就是一个上升的数组,例如下面这个 $n = 5$ 的数组,LIS 就取到了 $n = 5$ 的长度。

1
nums2 = [1, 2, 3, 4, 5]

由于有这样一个范围的限制,我们定义一个数组 vec,vec[i] 表示长度为 i 的上升子序列的最小结尾。

比如上面的 nums2 这个数组,它有若干个长度为 3 的上升子序列,例如 [1, 2, 3], [1, 2, 4], [2, 4, 5] 都是,但是 [1, 2, 3] 这个子序列是其中结尾最小的,那么 vec[3] = 3,类似地,我们可以推出 vec[4] = 4, vec[5] = 5

nums2 这个 $n = 5$ 数组整个就是上升的,所以 vec[1], vec[2], vec[3], vec[4], vec[5] 都能够取到值。

有的数组不是所有的 vec[1], vec[2], ..., vec[n] 都是能取到值的,比如 nums1,nums[2] 就已经取不到值了,因为它的 LIS 长度也仅仅才 1,长为 2 的上升子序列不存在,vec[2] 自然取不到值。

对于 nums,我们可以发现关于 vec 的以下两个特性:

  • 当某个 1 <= i <= n 可以取到 vec[i] 时,那对于 1 <= j < ivec[j] 也都能取到值;
  • 当某个 1 <= i <= n 无法取到 vec[i] 时,那对于 i < j <= nvec[j] 也无法取到值;

因此如果得到 nums 对应的 vec,其中在 1, 2, …, t 上有对应的取值,在 $t+1, t+2, …, n$ 上无法取到值。那么我们就求出了 LIS 的长度 $t$。

那问题就变成了:如何得到 vec。

初始时,vec[1..n] 均标记为一个特殊值,例如 INT_MAX

然后从 0 到 n - 1 枚举 i,对于 i 我们考察 nums[0..i] 上以 nums[i] 结尾的最长上升子序列,假设其长度为 len,此时考察 vec[len] 有以下是两种情况:

  • vec[len]INT_MAX,说明此前(枚举 0..i-1 时)还没有得到长为 len 的上升子序列。那么就将 vec[len] 改为 nums[i],表示 nums[0..i] 上长度为 len 的上升子序列的最小结尾为 nums[i],未来(枚举 i+1..n-1 时)有可能发现某个 i < j < n,以 nums[j] 结尾的最长上升子序列长度也为 len,但是 nums[j] < nums[i],那么这里的 vec[len] 就会从 nums[i] 更新为 nums[j]
  • vec[len] 为其它值,那么就看 nums[i] 是否小于 vec[len],如果小于,就将 vec[len] 更新为num[i]

当枚举到 i 时,vec[p] 的含义是 nums[0..i-1] 上长度为 p 的上升子序列的最小结尾。现在问题变成了:枚举到 i 时,如何得到 len 是多少。

我们先看 nums[0..i] 上以 nums[i] 结尾且长度为 len 的上升子序列存在需要满足什么条件。如果该子序列存在,那么它是由在 nums[0..i-1] 上的某个长为 len - 1 的上升子序列加上当前的 nums[i] 组成的。因此我们就看此时 vec[len-1],如果该值 < nums[i],则说明 nums[0..i-1] 上存在一个长为 len - 1 的上升子序列且其结尾小于 nums[i],那么nums[0..i] 上以 nums[i] 结尾且长度为 len 的上升子序列也就存在;否则就不存在。

于是问题变成了:满足 vec[len-1] < nums[i] 的最大的 len 是多少。

下面证明 vec 是单调递增的

反证:因为如果不递增,就存在某个 p1 < p2, vec[p1] >= vec[p2],对于 nums[0..i-1] 上以 vec[p2] 结尾的上升子序列 arr,arr[0..p1-1] 当然也就是 nums[0..i-1] 上的一个长为 p1 的上升子序列,该序列的结尾是 t = arr[p1-1],那么 t < vec[p2]。因此 t < vec[p1],这与 vec 的定义矛盾。$\Box$

因此我们可以二分地在 vec 上找到大于等于 nums[i] 的最小的位置 p,这个 p 就是我要求的 len。

基于以上分析,我们可以写出完整的算法,注意这里的算法中 vec 是从 0 开始的,也就是 vec[p] 表示的是长为 p + 1 的上升子序列最小结尾是 vec[p],并且只有当枚举到某个 i 时首次发现长为 p + 1 的上升子序列时(枚举 0..i-1 过程中上升子序列长度范围是 1 到 p),才将 nums[i] 插入到 vec 末尾,也就是 vec[p] = nums[i]

1
2
3
4
5
6
7
从前往后枚举 i
vec 始终为一个单调递增的数组,假设我们要把 nums[i] 插入到 vec 中,找到这个插入的位置 p
如果 p < vec.size():
则 vec[p] = nums[i]
否则:
vec.push_back(nums[i])
vec.size() 为 nums[0..n-1] 上 LIS 长度

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
vector<int> vec; // vec[i] 是长度为 i 的 LIS 的最小结尾
for(int i = 0; i < n; ++i)
{
// nums[i] 更新到 vec 中
int p = lower_bound(vec.begin(), vec.end(), nums[i]) - vec.begin(); // lower_bound 得到的是可以插入 nums[i] 的最小的位置
if((int)vec.size() > p)
vec[p] = nums[i];
else
vec.push_back(nums[i]);
}
return (int)vec.size();
}
};

Share