最长上升子序列

介绍

最长上升子序列指的是序列中最长的单调递增的子序列。

如对于序列 $[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;
}

例题