较小的结尾有什么用?
定义 14.2.1
(严格递增子序列)
的子序列保留原来的次序,但可以跳过元素;它由下标 决定。若 ,它就是严格递增的,即每个选中的值都小于下一个。
例如 是 的子序列, 却不是:6 出现在 2 和 4 之前。
对两条长度相同的递增子序列,结尾较小的一条至少同样容易由未来的值延长。这不表示前面的元素相同,也不表示一组尾值本身是一条子序列。有用的状态是:分别对每个长度记下最小可能结尾。
定义 14.2.2
(各长度的最小尾值)
对整数输入 ,令 为已处理前缀中,长度为 的严格递增子序列之最小可能末值。把 放在 tails 的位置 ; 是目前可达的最大长度。空前缀对应空数组。
尾值严格递增
定理 14.2.3
(最小尾值严格递增)
对每个已处理的前缀,都有 。
证明
(把最优的较长子序列与其前缀比较)
对 ,选一条长度 、末值为 的子序列。它的前 个选中元素构成长度 的子序列,其末值 严格小于 。因为 是长度 的最小可达末值,
所以 tails 严格递增。前缀有限,子序列也只有有限多条,因此各最小值确实存在。
这个次序允许二分搜索。读到新值 时,找首个 tails[j] >= x 的位置 j;若没有,令 j = len(tails)。以 替换该尾值,或在末端加入 。
定理 14.2.4
(每个元素只改变一个最小尾值)
设 j 为首个满足 tails[j] >= x 的位置;若没有,则 j 为 len(tails)。读入 后,长度 j+1 的最小尾值变为 (被替换,或在末端新增),而其他每个长度的最小尾值都不变。
证明
(只有长度 j 加一的状态可能改善)
读取 前,j 之前的尾值都小于 。若 j>0,可以把 接到一条以 tails[j-1] 结尾、长度为 j 的子序列;若 j=0, 本身构成长度一。因此长度 j+1、以 结尾的子序列存在。
对任何较短长度,旧的最小尾值已小于 ,以 结尾不会改善它。对大于 j+1 的长度,若有子序列以 结尾,其先前部分至少有长度 j+1 且末值小于 。若 j 位于旧数组内,该长度的最小尾值已至少为 ,产生矛盾;若 j 在末端,旧前缀根本没有更长的子序列。所以只有长度 j+1 的状态可能改善或新出现。替换或追加后,各项仍有原来的最小尾值意义。
证明透视
严格性与已排序性在哪里用到
这个证明依靠两个前面的事实。尾值严格单调,使二分搜索有效,并给出“j 之前的尾值都小于 ,而 tails[j] 不是”。不平凡的一步在最后:若有长度大于 j+1 且以 结尾的子序列,它会含有一条长度 j+1、末值严格小于 的前缀,而 tails[j] >= x 排除了这种情形,所以更长的状态不会改变。“首个至少等于”的规则正是严格性所需要的:等于 的尾值不能被 延长,所以必须被替换而不是跳过。若改用“首个严格大于”的规则,证明就会在“接在每个更短的尾值之后都可以以 结尾”处失效。
须找第一个至少等于 的尾值,而非第一个严格大于 的尾值。相等值不能延长严格递增子序列。对 ,尾值数组始终为 ,答案是一。非递减子序列是不同问题,应找第一个严格大于 的尾值。
概念视角组合
尾值就是各堆的堆顶
把每个项目放到最左边、堆顶至少为 的一堆上;若没有这样的堆,就开一个新堆。于是每一堆都是非递增的,而各堆堆顶正是 tails。对 ,各堆为 、、。递增子序列中的两项不会落在同一堆,所以 堆就证明不存在长于 的递增子序列。
常见错误
(对严格链使用首个严格大于的尾值)
若以 bisect_right 代替 bisect_left,输入 会得到 bisect_right([2],2)=1,于是再次追加 ,尾值变成 ,再变成 。报告的长度 是错的:任何两个相等的值都不能构成严格递增子序列,正确的长度为 。
尾值数组不一定是子序列
反例模式
各最小尾值的见证可能互不相容
依次处理 ,尾值数组为
最后 虽然递增,其来源下标依次是 3、4、2(从零开始),不是输入的子序列。尾值 6 的长度三见证是 ;后来较短长度的替换是独立最优值。
数组长度仍给出正确的最大长度。要输出实际下标,须在每个元素处理时,记录它延长了哪个较早的见证。
替换尾值时保存见证
以 end[j] 记录达到 tails[j] 的一条见证之末项输入下标;prev[i] 记录第 项选用的前驱下标。当 放入 j>0 时,先设置 prev[i] = end[j-1],然后才替换尾值或末项下标。若 j=0,便没有前驱;接着设置 end[j]=i,必要时追加。
定理 14.2.5
(已记录的前驱链给出最优见证)
设 end[j] 与 prev 如上维护。每处理一个元素后,end[j] 都是一条真实的、长度为 j+1、末值为 tails[j] 的严格递增子序列的末项下标。从 end[L-1] 沿 prev 回溯并反转,得到最大长度 的严格递增子序列。
证明
(后来的替换不会破坏已记录的前驱链)
按输入位置归纳。每个 end[j] 都指向已处理前缀中一条真实的长度 j+1 递增子序列,其末值是 tails[j]。若新位置 j>0,end[j-1] 的见证更早出现,末值又严格小于 ;接上当前元素得到有效的长度 j+1 见证。j=0 则是一项见证。
新的 prev[i] 存储固定的输入下标,不是指向可变的尾值槽位。之后即使 end[j-1] 改变,也不会改变已记录的前驱。从最后的 end[L-1] 沿链回溯并反转,得到下标严格递增、值也严格递增的子序列。它有长度 ,而尾值不变量已证明这是最优长度。
from bisect import bisect_left
def longest_increasing_subsequence(a):
tails, end = [], []
prev = [-1] * len(a)
for i, x in enumerate(a):
j = bisect_left(tails, x)
if j > 0:
prev[i] = end[j - 1]
if j == len(tails):
tails.append(x)
end.append(i)
else:
tails[j] = x
end[j] = i
indices = []
current = end[-1] if end else -1
while current != -1:
indices.append(current)
current = prev[current]
indices.reverse()
return indices, [a[i] for i in indices]
例题 14.2.6
(在短输入上追踪三个数组)
对 运行程序,记录每个元素之后的 tails、end 和新的 prev。
| 元素 | j | prev[i] | tails | end | |
|---|---|---|---|---|---|
| 0 | 3 | 0 | |||
| 1 | 5 | 1 | 0 | ||
| 2 | 6 | 2 | 1 | ||
| 3 | 2 | 0 | |||
| 4 | 4 | 1 | 3 |
最后 end[2]=2,prev[2]=1,prev[1]=0,所以见证下标为 ,值为 。下标 处的值 的前驱下标是 ,构成有效的长度为二的链 ,虽然这条链没有延长到长度三。
例题 14.2.7
(相等值:一个边界情形)
对 ,第一个元素给出 tails 和 end 。对 ,首个至少为 的尾值在位置 ,所以该尾值被 替换,prev[1]=-1,end[0]=1,对下标 同样处理。最终 tails 为 ,长度为 ,重建返回下标 和值 。空输入使 end 为空,current=-1,并返回两个空列表。
例题 14.2.8
(替换尾值不得破坏已记录的链)
对 运行程序。元素 :tails 。元素 (,j=0):tails ,end 。元素 (,j=1):prev[2]=end[0]=1,tails ,end 。元素 (,j=1):prev[3]=end[0]=1,并替换 :tails ,end 。元素 (,j=2):prev[4]=end[1]=3,所以 tails ,end 。从下标 沿链回溯得 ,下标为 ,值为 。链接 prev[4]=3 指向长度为二的当前持有者 ,而不是下标 处已被替换的值 。
输入须为整数序列;函数不修改它。结果是一组最优下标及其值,不保证字典序最小。空输入返回两个空列表。对 ,最终长度三的末项仍是下标 2,沿已记录前驱可得下标 和值 。
计算工作量和输出
命题 14.2.9
(尾值搜索的成本)
对 个元素,此实现需要 次比较及 个存储项;重建长度 的见证需 时间。
证明
(二分搜索与存储数组)
个元素各在至多 项的数组中做一次二分搜索,需要 次比较,另加常数次赋值。数组 tails、end、prev 及输出的下标列表各至多有 项。重建时每一步沿链走一步,共 步,再反转长度为 的列表。
这些是项数和比较次数的界;任意大整数比较的位运算成本须另行计算。只求长度时可以省略前驱数组,但输出见证需要额外的信息与正确性论证。
此方法不计算最优子序列的数量;带权重或间距限制的变体也须修改状态及证明。“严格递增”决定二分比较和见证条件。
常见错误
(期望得到某个特定的最优解)
对 , 和 的长度都是最优的三。程序把长度为二的尾值 替换为 ,返回下标 ,即 。该算法证明得到的是一条最长链,而不是字典序最小或最早的那一条。
练习与解答
快速检查
(处理 。严格版本的答案是多少?非递减版本呢?)
逐个元素追踪尾值数组。
解答 · 答案
tails 始终为 ,严格长度为 1。三个值可构成长度为 3 的非递减子序列;更新须找首个大于 的尾值。
快速检查
(为什么 不是 的有效见证?)
看看这三个值在输入中的位置。
解答 · 答案
来源下标是 ,并非递增;各个最优尾值未必来自同一条按时间顺序的链。
快速检查
(为 给出最优见证,并解释后来替换尾值为什么不破坏它。)
处理 和 时记录了哪些链接?
解答 · 答案
下标 给出 。处理 5 和 6 时记录的前驱下标,不会因后来替换长度为一、二的末项而改变。
快速检查
(为什么严格递增使用 bisect_left?)
当 等于某个现有尾值时应该怎样?
解答 · 答案
它替换第一个等于 的尾值,而不是追加相等值;严格递增链只能延长小于 的尾值。
快速检查
(给出处理 之后的 tails 及所报告的长度。)
每个元素都不大于现有的尾值。
解答 · 答案
处理 后为 。对 ,首个至少为 的尾值在位置 ,得 ;对 得 。报告的长度为 ,这是正确的,因为没有任何两个值是递增的。
证明分成两层:最小尾值保证最优长度,固定的前驱下标则提供达到该长度的真实子序列。