PYTHON LESSON 108
例题精练：最长上升子序列两次跃迁
以 LIS 为例练透“先朴素后优化、两版对拍”的解题节奏，理解 tails 数组的替换逻辑。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- dp[i] 以第 i 个数结尾的 LIS 长度
- tails[k] 存长度为 k+1 的序列的最小结尾
- bisect_left(tails, x) 二分找替换位置
01 · 核心概念
同一道题的两档解法：O(n²) 与 O(n log n)
同一道题的两档解法：O(n²) 与 O(n log n)：给一串数字，找最长的严格上升子序列（可跳选、顺序不能变）。动笔前先手工举小例：3 1 4 1 5 9 2 6 里能挑出 1 4 5 9，长度 4。有了具体例子，后面每一步都有对照。
GESP Python 7 级 · 最长上升子序列 LISGESP Python 7 级 · 二分优化复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
dp[i] 以第 i 个数结尾的 LIS 长度先准确读出这条写法的结构与作用。
tails[k] 存长度为 k+1 的序列的最小结尾换一组最小数据，手工推演一次结果。
bisect_left(tails, x) 二分找替换位置再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 例题精练：最长上升子序列——从 O(n^2) 到 O(n log n)
from bisect import bisect_left
nums = [3, 1, 4, 1, 5, 9, 2, 6]
# 解法一：动态规划 O(n^2)，n 在几千以内就够用
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)
ans1 = max(dp)
# 解法二：tails + 二分 O(n log n)，n 到 10 万也不怕
tails = []
for x in nums:
p = bisect_left(tails, x)
if p == len(tails):
tails.append(x)
else:
tails[p] = x
ans2 = len(tails)
print("序列：", nums)
print("DP 表：", dp)
print("O(n^2) 答案：", ans1)
print("tails 数组：", tails)
print("O(n log n) 答案：", ans2)序列： [3, 1, 4, 1, 5, 9, 2, 6] DP 表： [1, 1, 2, 1, 3, 4, 2, 4] O(n^2) 答案： 4 tails 数组： [1, 2, 5, 6] O(n log n) 答案： 4
两种解法答案一致（都是 4，如子序列 1 4 5 9）；tails 本身不一定是合法子序列，但它的长度一定是答案。
04 · 逐步理解
每一步只解决一个问题
- 01
读题先造数
给一串数字，找最长的严格上升子序列（可跳选、顺序不能变）。动笔前先手工举小例：3 1 4 1 5 9 2 6 里能挑出 1 4 5 9，长度 4。有了具体例子，后面每一步都有对照。
- 02
第一版：O(n²) 的 DP 保底
dp[i] 表示以 nums[i] 结尾的最长上升子序列长度。枚举前面的每个 j，只要 nums[j] 更小就能接上。每个数自己就是长度 1，所以 dp 初始全 1；答案是 max(dp)，不是最后一项。
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 表
对着 dp 表 [1,1,2,1,3,4,2,4] 抽查一项：数字 5 对应 3，因为前面比它小的有 1、4、1，其中最大的 dp 是 4 对应的 2，接上去得 3。每个数都这样问一遍，表就不会错。
- 04
数据变大：n² 撑不住了
n 到 10 万时 n² 是 10¹⁰ 次操作，必超时。优化的关键观察：同样长度的上升序列，结尾越小，未来越容易接新数。于是维护 tails 数组：tails[k] 记录长度为 k+1 的序列里最小的结尾值。
- 05
第二版：tails + 二分
逐个读入 x：用 bisect_left 在 tails 里找第一个 ≥ x 的位置，替换掉它（让结尾更小）；x 比所有结尾都大就追加到末尾（序列变长）。tails 始终有序所以能二分，len(tails) 就是答案。
p = bisect_left(tails, x) if p == len(tails): tails.append(x) else: tails[p] = x - 06
两版对拍：考场查错神器
考场上先写 O(n²) 保底拿部分分，再写二分版冲满分。造若干组随机小数据，两份代码各跑一遍比对答案——这就是“对拍”。两版输出不一致时，多半是新写法有 bug，拿小数据一调一个准。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，确认两种解法答案一致
- 2手工核对 dp 表中数字 5 对应的那个 3
- 3把序列改成全降序，预测两种解法的输出
- 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) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
算法方法动态规划、贪心与分治根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。＋
正式定义
动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。
必须掌握
- DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。
- 记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。
- 滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。
- 贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。
- 归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。
- LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。
常见误区
- 状态定义不含必要信息
- 转移顺序读取到本轮新值
- 没有证明就使用贪心
- 把连续子数组和子序列混为一谈
适用边界
- 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
- DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。
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 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
完成检查