BM71　最长上升子序列(一)¶

中等通过率 25.43%python3核心代码模式样例通过牛客 AC动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

维护「长度 -> 最小结尾」的单调数组，二分替换。

解题思路¶

这题考什么¶

LIS（最长上升子序列，删去若干元素后剩下的严格递增序列里最长的那条）的两种状态设计，以及换一个状态定义就能把复杂度整档降下来的思路，见线性 DP。

朴素 DP：dp[i] = 以 arr[i] 结尾的最长上升子序列长度。

dp[i] = max(dp[j] + 1)   其中 j < i 且 arr[j] < arr[i]；没有这样的 j 时 dp[i] = 1

答案是 max(dp)。它是 O(n^2)，本题允许，但状态里塞了「结尾在哪个下标」这个多余信息。

贪心 + 二分：换成 tails[k] = 所有长度为 k+1 的上升子序列里最小的结尾值。只关心「每种长度能做到多小的结尾」，把 n 个状态压成至多 n 个但按长度索引的数组。 tails 天然严格递增：长度更长的子序列，其最优结尾一定更大。逐个扫 arr[i]：

在 tails 里二分找第一个 >= arr[i] 的位置 p
p == len(tails)  ->  arr[i] 比所有结尾都大，可以接在最长的那条后面，长度加一
否则             ->  用 arr[i] 覆盖 tails[p]，长度 p+1 的结尾变得更小

覆盖不会让答案变差：结尾越小，后面越容易接得上，而已有长度一个都没丢。扫完之后 tails 的长度就是答案。

等号位置是唯一的思维点：本题要求严格上升，所以找第一个 >= arr[i] 的位置，用 bisect_left——相等的结尾值必须被顶掉，留着它就允许接出相等的相邻项。若改成最长不下降（允许相等），则要找第一个 > arr[i] 的位置，用 bisect_right。

数据规模与复杂度¶

0 <= n <= 1000，时限 2 秒（其他语言）。朴素 DP 是 1e6 次内层迭代，在时限内也能过；这里的贪心加二分只有 n log n 约 1e4 次操作，时间 O(n log n)、空间 O(n)，与题面要求的 O(n^2) 时间、O(n) 空间相比只优不劣。

坑在哪¶

tails 不是那条最长上升子序列本身，只是「每种长度的最优结尾值」。它的元素可能来自不同时刻、拼不成一条真实的子序列，拿它去还原方案会得到错误的序列；要还原方案得另记每个元素被放进的长度再回溯。
bisect_left 与 bisect_right 只差在相等元素的落点，却对应两道不同的题：严格上升用 left，不下降用 right。选错时 [1,1,1] 会被答成 3 而不是 1。
覆盖用的是赋值而不是插入。tails 的长度只在「接到最长的后面」时才增长，用 insert 会把数组撑长，答案偏大。
n == 0 时循环不进，返回 len(tails) = 0，与题面的空数组情形一致。

样例复核¶

[6,3,1,5,2,3,7]：tails 依次是 [6] -> [3] -> [1] -> [1,5] -> [1,2] -> [1,2,3] -> [1,2,3,7]，长度 4，与期望输出一致（对应子序列 [1,2,3,7]）。

参考实现¶

solutions/nowcoder/BM71/sol.py
from bisect import bisect_left
from typing import List, Optional


class Solution:
    def LIS(self, arr: List[int]) -> int:
        # tails[k]：所有长度为 k+1 的上升子序列里最小的结尾值。它始终严格递增，故可二分
        tails: List[int] = []
        for x in arr:
            # 严格上升：找第一个 >= x 的位置，相等的结尾也要被顶掉，所以用 left 而非 right
            p = bisect_left(tails, x)
            if p == len(tails):
                tails.append(x)     # x 大于所有结尾值，接在最长的那条后面，答案长度加一
            else:
                # 覆盖而非插入：长度 p+1 的最优结尾变小，后面更容易接上，已有长度一个不丢
                tails[p] = x
        return len(tails)           # 数组长度即最长上升子序列的长度

BM71 最长上升子序列(一)¶