介绍
最长上升子序列指的是序列中最长的单调递增的子序列。
如对于序列 $[2,5,3,4,1,7,6]
$,它的最长上升子序列为 $[2,3,4,7]
$ 和 $[2,3,4,6]
$。
$\mathcal{O}(n^2)
$ 复杂度的算法
1
2
3
4
5
6
7
8
9
10
11
12
|
def LIS(nums: List[int]) -> List[int]:
n = len(nums)
p = [1] * n
for i in range(1, n):
t = 0
for j in range(i):
if nums[i] > nums[j] and p[j] > t:
t = p[j]
p[i] = t + 1
return p
|
$\mathcal{O}(n\log(n))
$ 复杂度的算法
记录一个额外的递增序列 栈 $s
$,如果当前元素 $x
$ 大于栈顶元素,直接将该元素 push
到栈中,否则,将栈中最近的一个大于等于 $x
$ 的元素替换为 $x
$。经过这样的操作,不会对最长上升子序列有影响,而通过使用二分查找递增的序列,可以将时间复杂度降低到 $\mathcal{O}(n\log(n))
$。
$$ \begin{array}{c}
2&5&3&4&1&7&6\\\hline
2&2&2&2&1&1&1\\
&5&3&3&3&3&3\\
&&&4&4&4&4\\
&&&&&7&6
\end{array} $$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
from bisect import bisect_left
from typing import List
def LIS(nums: List[int]) -> List[int]:
p = [0] * len(nums)
s = []
for i, x in enumerate(nums):
if not s or x > s[-1]:
s.append(x)
p[i] = len(s)
else:
k = bisect_left(s, x)
s[k] = x
p[i] = k + 1
return p
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
vector<int> LIS(vector<int> &nums) {
vector<int> s, res;
for (auto &x : nums) {
if (s.empty() || x > s.back()) {
s.emplace_back(x), res.emplace_back(s.size());
} else {
auto it = lower_bound(s.begin(), s.end(), x);
*it = x, res.emplace_back(it - s.begin() + 1);
}
}
return res;
}
|
例题