跳转至

最长上升子序列#
发布于2020-11-29
上次编辑2021-04-19

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

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

例题#

返回顶部

在手机上阅读