PYTHON LESSON 103
最长上升子序列
掌握 LIS 的 O(n²) 动态规划解法，理解 tails + 二分的 O(n log n) 优化思路。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- dp[i]：以第 i 个数结尾的 LIS 长度
- if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1)
- bisect_left(tails, x) 二分找替换位置
01 · 核心概念
LIS：动态规划与二分优化
LIS：动态规划与二分优化：子串必须连续，子序列只要相对顺序不变、可以跳着选。从 10 9 2 5 3 7 101 18 里选出 2 3 7 18，就是一条长度为 4 的上升子序列。先理解题意，再谈算法。
GESP Python 7 级 · 最长上升子序列 LISGESP Python 7 级 · 复杂动态规划复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
dp[i]：以第 i 个数结尾的 LIS 长度先准确读出这条写法的结构与作用。
if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1)换一组最小数据，手工推演一次结果。
bisect_left(tails, x) 二分找替换位置再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 最长上升子序列（LIS）：DP 逐个决策
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# dp[i] 表示“以第 i 个数结尾”的最长上升子序列长度
dp = [1] * len(nums) # 每个数自己就是长度为 1 的序列
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
print("序列：", nums)
print("dp 表：", dp)
print("最长上升子序列长度：", max(dp))序列： [10, 9, 2, 5, 3, 7, 101, 18] dp 表： [1, 1, 1, 2, 2, 3, 4, 4] 最长上升子序列长度： 4
子序列可以不连续，但相对顺序必须和原序列一致；“严格上升”用 < 判断。
04 · 逐步理解
每一步只解决一个问题
- 01
子序列与子串不一样
子串必须连续，子序列只要相对顺序不变、可以跳着选。从 10 9 2 5 3 7 101 18 里选出 2 3 7 18，就是一条长度为 4 的上升子序列。先理解题意，再谈算法。
- 02
状态：盯住“结尾”
dp[i] 定义为“以 nums[i] 结尾”的最长上升子序列长度。盯住结尾，转移就好写：枚举前面所有 j < i，只要 nums[j] < nums[i]，就能把 nums[i] 接在 j 的序列后面。
dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) - 03
答案是整个 dp 表的最大值
最长上升子序列可以以任何位置结尾，所以答案是 max(dp)，不是 dp[-1]。初始全 1 的含义也很关键：每个数独自就是长度 1 的合法序列。
print(max(dp)) - 04
O(n²) 不够用怎么办
双重循环是 n² 量级，n = 10⁵ 就是 10¹⁰ 次操作，必超时。优化的钥匙是一个叫 tails 的数组：tails[k] 记录“长度为 k+1 的上升子序列里，最小的结尾值”。
- 05
tails + 二分：O(n log n)
逐个读入 x：在 tails 里二分找第一个 ≥ x 的位置，替换掉它（让同样长度的序列结尾更小、未来更好接）；如果 x 比所有结尾都大，就追加到末尾（序列变长）。tails 始终有序，二分找位置用 bisect_left，答案就是 len(tails)。
from bisect import bisect_left tails = [] for x in nums: p = bisect_left(tails, x) if p == len(tails): tails.append(x) else: tails[p] = x - 06
严格上升用 bisect_left
bisect_left 找“第一个 ≥ x”的位置，相等的数会替换掉旧值而不是接在后面——正好实现“严格”上升。如果题目允许相等（不降序列），换成 bisect_right 即可，一字之差，语义全变。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，手工核对 dp 表每一项
- 2把序列改成全降序，看答案变成什么
- 3在 dp 表上圈出一条最长上升子序列
- 4说说 tails 数组为什么能保持上升
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法动态规划、贪心与分治根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。＋
正式定义
动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。
必须掌握
- DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。
- 记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。
- 滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。
- 贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。
- 归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。
- LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。
常见误区
- 状态定义不含必要信息
- 转移顺序读取到本轮新值
- 没有证明就使用贪心
- 把连续子数组和子序列混为一谈
适用边界
- 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
- DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。
程序组织模块、导入与常用标准库正确导入模块，并按用途查找 math、random、statistics、collections、heapq、bisect 等标准工具。＋
正式定义
模块是可导入的 Python 代码单元，包把模块组织成层次。import 先加载模块并创建模块对象，再把名字绑定到当前命名空间；标准库随 Python 分发，不等于第三方包。
必须掌握
- import module 保留清晰命名空间；from module import name 只导入指定名字；避免 from module import *。
- math 提供 sqrt、floor、ceil、gcd、log、sin 等数学函数和 pi、e 等常量。
- random 用于伪随机模拟，不适合密码安全；需要安全随机时使用 secrets。
- collections.deque 适合双端队列，Counter 适合计数，defaultdict 可按工厂创建缺省值。
- heapq 实现最小堆，bisect 在已排序序列中二分定位，itertools 提供高效迭代组合工具。
- if __name__ == '__main__': 用来区分文件被直接运行还是被导入。
常见误区
- 文件名写成 math.py 导致遮蔽标准库
- import * 污染命名空间
- 把 random 当成加密随机数
- 没有理解工具的数据复杂度就盲目调用
适用边界
- 标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
- Turtle 需要图形窗口，本站文本判题环境不伪造其画布。
完成检查