最长递增子序列 - Ciallo Wiki

1 概念与问题定义

1.1 序列、子序列与严格递增

最长递增子序列（LIS）问题以一个给定序列为输入。设序列为 \(a_1,a_2,\dots,a_n\)。从中选择若干个下标 \(1 \le i_1<i_2<\cdots<i_k\)，组成子序列 \(a_{i_1},a_{i_2},\dots,a_{i_k}\)。子序列保持原序列的相对顺序，但不要求元素在原序列中相邻。

所谓“严格递增”是指子序列相邻元素满足 \[ a_{i_1}<a_{i_2}<\cdots<a_{i_k}. \] LIS 的目标是使 \(k\) 取到最大值，因此答案对应的是最长长度的严格递增子序列。

1.2 常见变体：非严格递增与自定义比较关系

在实际场景中，递增关系可能采用非严格形式或自定义比较规则。

非严格递增：将条件从 \(<\) 改为 \(\le\)，即允许相等值连续出现，这会得到“最长非递减子序列”（常记为 LNDS），在很多任务中更符合业务含义。
自定义比较：若元素不一定是数值，而是可比较对象（例如按某字段排序的结构体），可以定义“前者是否应当排在后者之前”的比较函数；此时 LIS 在逻辑上仍成立，只要比较关系能提供一致的“大小”或“先后”判断。

1.3 目标：仅求长度还是恢复方案

LIS 问题常见两类输出形式：

只求长度：输出最大 \(k\)，不关心具体选了哪些下标。
恢复方案：输出某个达到最大长度的递增子序列（及其下标），或在需要时恢复全部方案（后者通常复杂度更高）。

在算法设计上，这两类目标会影响信息是否需要额外记录，例如动态规划中是否要保存前驱，贪心二分方法中是否要维护回溯索引。

1.4 相关指标：计数、方案数与最小结尾策略

除了长度之外，还可能关心：

方案数/计数：有多少个不同的最优子序列（通常按下标序列区分）。计数往往需要在动态规划转移中对路径数进行累加，并处理重叠。
最小结尾策略：在二分/贪心思想中，会维护长度为 \(k\) 的递增子序列的“最小可能结尾值”。这种策略并非只为简化，而是保证后续扩展更“宽容”，从而维持最优结构。

2 动态规划方法

2.1 状态表示与最优子结构

动态规划将“以某位置结尾的最优解”作为核心状态，从而利用最优子结构。

2.1.1 以位置为结点的递推定义

令 \(dp[i]\) 表示“以位置 \(i\) 作为结尾”的最长严格递增子序列长度，即在子序列中最后一个元素必须是 \(a_i\)。则答案为 \(\max_i dp[i]\)。

递推思路是：若要让 \(a_i\) 成为结尾，则前一个元素必须来自某个位置 \(j<i\)，且满足 \(a_j<a_i\)。因此 \[ dp[i]=1+\max\{dp[j]\mid j<i,\ a_j<a_i\}, \] 若不存在满足条件的 \(j\)，则 \(dp[i]=1\)。

2.1.2 处理重复元素的规则

严格递增要求前一个元素必须小于当前值，因此重复元素之间不能互相接在同一条递增链上。对应到递推条件就是严格比较 \(a_j<a_i\)；当序列中出现相同值时，可能导致某些 \(dp[i]\) 只能从更小的前驱继承，或只能从自身开始。

2.2 经典 O(n^2) 解法

2.2.1 转移方程推导

按照上述递推，直接枚举每个位置 \(i\) 的所有可能前驱 \(j\)。伪代码结构通常为：

初始化所有 \(dp[i]=1\)；
对每个 \(i\)，遍历 \(j=1..i-1\)，若 \(a_j<a_i\)，则更新 \(dp[i]=\max(dp[i],dp[j]+1)\)；
最终取 \(\max_i dp[i]\)。

该方法直观、实现简单，适合用于学习与中小规模数据。

2.2.2 时间与空间复杂度分析

时间复杂度：外层 \(n\)，内层最多 \(n\)，整体为 \(O(n^2)\)。
空间复杂度：只需保存 \(dp\) 数组，通常为 \(O(n)\)。若还要恢复方案，可能额外保存前驱指针，仍为 \(O(n)\)。

2.3 恢复最长递增子序列

求出长度之后，若希望得到具体序列，需要额外记录“最佳前驱是谁”。

2.3.1 前驱指针的记录

可维护数组 pre[i]，表示当 \(dp[i]\) 取得最优时，前一个位置 \(j\) 的下标。更新逻辑为：

当找到更大的 \(dp[j]+1\) 时，令 pre[i]=j；
若出现并列最优，也可以按某种规则决定保留哪一个前驱（见下节）。

最后从使得 dp[i] 最大的某个终点开始，沿着 pre 指针回溯，得到子序列的下标序列，反转即可。

2.3.2 多解时的选取策略

当存在多个前驱都能得到同样的最优长度时，恢复出来的子序列可能不同。常见策略包括：

按最早/最晚下标选择：用更新时的遍历顺序决定，例如先遇到就保留或后遇到就覆盖。
按值大小偏好：在严格递增下，偏好更小的前驱可能更稳定；不过要保证不破坏长度最优性。

百科式结论是：恢复多解时，应明确“选择准则”，否则同样输入可能产生不同输出。

2.4 复杂度与边界情况

2.4.1 空序列与全降序

空序列：若输入长度为 0，则 LIS 长度通常定义为 0，恢复方案为空。
全降序：若序列单调递减，则任何严格递增子序列都只能取长度 1。动态规划中每个位置都无法从前驱继承更长链，因此 \(dp[i]=1\)。

2.4.2 全相等序列与重复值

若所有元素相同且要求严格递增，则同样只能取长度 1。由于条件 \(a_j<a_i\) 永远不成立，前驱无法连接，恢复结果会是任意一个单元素子序列（具体取哪个取决于恢复策略）。

3 贪心 + 二分查找（耐心排序思想）

3.1 核心不变量：tails 数组的含义

在 \(O(n\log n)\) 的方案中，不再显式枚举所有前驱，而是维护一个“压缩后的状态”。核心是 tails 数组：其含义是对每个长度 \(k\)，记录一个尽可能“理想”的结尾值，使得存在长度为 \(k\) 的严格递增子序列，并且该结尾值尽量小。

3.1.1 tails[k] 代表的最小结尾

可将 tails 视为有序列表。定义方式常见为：

tails[len-1] 表示：长度为 len 的严格递增子序列中，最小可能的结尾值；
数组按结尾值单调递增，因此能够二分查找。

当遍历到一个新元素 \(x\) 时，我们要做的是：找到可以让 \(x\) 成为某个长度的结尾的合适位置，从而更新 tails。

3.1.2 严格递增条件下的更新规则

严格递增要求下一元素必须大于当前结尾，因此在寻找插入位置时，需要采用与“是否允许相等”一致的边界规则。对于严格递增，通常使用“找到第一个大于等于 \(x\) 的位置并替换”，即：

若 tails 中存在值 \(\ge x\)，则用 \(x\) 替换该位置的结尾值；
若所有尾值都小于 \(x\)，则将 \(x\) 追加到 tails 末尾，形成更长的序列。

这个替换不改变可达的长度上界，但可能让结尾更小，从而为未来元素提供更多扩展空间。

3.2 二分查找更新 tails

3.2.1 查找插入位置与替换含义

二分查找返回一个位置 pos，满足 tails[pos-1] < x <= tails[pos]（以严格递增实现为例）。替换 tails[pos]=x 的意义是：我们找到了长度为 pos+1 的递增子序列，且其结尾值可以通过当前元素得到一个更优（更小）的选择。

替换并非“删掉旧方案”，而是把状态压缩到“最小结尾值”这一代表信息上。

3.2.2 处理重复元素的二分边界选择

重复元素在严格递增与非严格递增下边界选择不同：

严格递增：通常用“lower_bound（第一个 \(\ge x\)）”方式，以避免相等值把长度错误地扩展。
非严格递增：通常改为“upper_bound（第一个 \(>x\)）”，允许相等值接上形成更长的非递减链。

这也是实现中最常见的细节来源。

3.3 计算 LIS 长度的 O(n log n) 算法

3.3.1 算法流程概览

典型流程为：

初始化空的 tails；
依次遍历序列元素 \(x\)：

在 tails 中二分查找其应替换/插入的位置 pos；
若 pos 在数组末端，则追加；否则替换；

遍历结束后，tails 的长度即为 LIS 的长度（严格递增版本）。

3.3.2 典型例子走读（含“梗式”直觉解释）

例如序列 [3,1,2]：

看到 3：tails=[3]
看到 1：替换为更小结尾，tails=[1]
看到 2：追加形成更长，tails=[1,2]

直觉上可以把 tails 理解成“每种长度都要找一个最省心的结尾”。结尾值越小，就越不挑后续元素——这是一种“后面谁来都能接”的省事感。

3.4 从 tails 恢复实际子序列

长度算法本身只给出结果大小；要恢复序列，需要把“状态代表”对应到实际下标。

3.4.1 记录位置索引的做法

常见做法是在更新 tails 时同步记录：

tailsIndex[len-1]：表示当前长度为 len 的递增子序列，其最小结尾值来自原序列的哪个下标；
pre[i]：表示位置 i 作为结尾时的前驱下标。

当二分得到 pos（即新长度为 pos+1）时：

若 pos==0，则 pre[i] 设为 -1；
否则 pre[i] = tailsIndex[pos-1]；
然后用 i 更新 tailsIndex[pos]（即该长度的最小结尾对应的下标）。

3.4.2 前驱数组与回溯构造

最终取 tailsIndex[lastLen-1] 作为终点，沿着 pre 指针不断回溯得到下标序列。回溯得到的是逆序，再反转即可得到某个 LIS。

需要注意：由于 tails 的状态是“压缩代表”，恢复出来的子序列通常是某个最优解，而不保证是字典序最小或其他特定排序意义下的唯一解。

4 理论性质与等价表述

4.1 与耐心排序的等价

二分更新 tails 的过程与“耐心排序”思想高度同构：耐心排序将元素逐一放入若干“牌堆”中，并保持牌堆顶牌的单调性质；牌堆数量对应的就是 LIS 长度。tails 可以视作牌堆顶牌值的抽象表示。

这种等价性解释了为何算法会得到正确长度：它背后维护的是一个与递增链相关的结构计数。

4.2 与部分有序集（poset）视角的关联

将下标按自然顺序看作“前后约束”，并用数值比较建立关系，可以构造一个偏序集。LIS 的递增链对应于 poset 中的“有序链”（chain）的最长长度。这样一来，LIS 不只是数值问题，也可被理解为“最长链”问题在特定偏序关系下的体现。

4.3 与 Dilworth 定理 / 相关组合观点的直观联系（入门级）

在组合理论中，偏序集的链与反链之间存在深刻关系。Dilworth 定理在直觉层面表达了：最长链的长度与最少需要多少个“互不相容的集合”之间存在对偶联系。对于 LIS，可把严格递增子序列看作链，把与递增关系冲突的元素组看作反链或相关的互斥集合，从而在入门层面建立“结构分解”的直观图景。

这里的关键不是展开定理的完整证明，而是理解：LIS 的可计算性背后与更一般的偏序结构一致。

4.4 稳定性与比较操作对结果的影响

LIS 的结果对比较规则高度敏感：

改变严格/非严格边界会直接影响可扩展性；
自定义比较若不满足一致性，可能使“递增链”的定义不再形成可靠的偏序，从而破坏算法前提；
当比较器引入“等价类”时，需要明确等价对象能否串联，这与二分边界的处理对应。

因此，讨论稳定性时应先回到比较规则是否形成合理的“可传递的先后关系”。

5 应用场景

5.1 序列分析与趋势抽取

在时间序列或测量数据中，LIS 可用于抽取“保持上升趋势”的最长片段（非连续）。这类抽取常作为趋势检测的基础模块：例如温度传感器、销量变化或学习曲线中寻找最长的“持续改善段”。

5.2 版本演化与时间顺序约束（索引映射）

软件版本、事件流或日志往往包含“时间顺序”和“相对指标”。通过将事件映射为可比较的数值或等级，LIS 能帮助识别在索引意义下满足顺序约束的最长链，从而用于回放某类依赖关系或演化路径。

5.3 排队与调度中的序列最优子结构

在调度任务中，存在“先做某类再做另一类”的约束，常可建模为递增链问题。LIS 的动态规划与贪心结构提供了“最优子结构”范式：某条最优调度的后半段往往可以由更短的最优子问题构成。

5.4 数据挖掘中的“单调骨架”提取

数据挖掘中常需要从噪声序列中抽取“单调骨架”，用于解释或特征构造。LIS 提供了一种可验证、可恢复的骨架抽取方式：用相对有序的信息替代原始波动，进而降低建模复杂度。

6 算法实现要点

6.1 坐标压缩与可比较对象的映射

若输入元素是离散但可比较的（例如字符串类别、稀疏坐标），可先将其映射为可比较的整数或排序等级。坐标压缩的价值在于：

便于实现二分；
降低比较成本；
使算法与数据类型解耦。

需要注意的是：压缩映射应保持比较关系的同构性，即相对大小不能被破坏。

6.2 严格/非严格递增的差异化实现

实现时应把边界策略写死在二分函数中：

严格递增：使用“第一个 \(\ge x\)”的边界；
非严格递增：使用“第一个 \(>x\)”的边界。

此外，动态规划版中比较条件对应 \(a_j<a_i\) 或 \(a_j\le a_i\)。两处要保持一致，否则会得到不同定义下的答案。

6.3 性能优化与边界处理

6.3.1 大数据下的内存布局

在大规模输入下，常见优化包括：

tails 和索引数组用连续内存结构以提升缓存友好性；
尽量避免频繁的动态扩容，预估长度或使用固定上界数组；
对恢复方案的 pre 数组保留必要信息，其余可按需释放。

严格来说，这属于工程层面的“实现细节正确性”，其核心仍是保持状态一致。

6.3.2 常见错误：二分区间写错导致偏差

常见坑包括：

二分区间采用半开闭区间但更新时用错边界；
返回位置使用错误的 pos 含义（比如把“插入点”与“替换点”混为一谈）；
在严格/非严格版本之间未同步修改二分边界。

这些错误通常会导致 LIS 长度偏大或偏小，尤其在存在大量重复元素时表现更明显。

6.4 单元测试建议与样例集

建议测试集覆盖：

空序列、长度为 1 的序列；
全降序、全升序、全相等；
含重复值的混合序列；
随机序列与可手算的小样本，用于比对恢复出的具体序列是否确实递增且长度最优。

对恢复功能，还应验证回溯得到的下标满足递增条件，并且其长度等于计算得到的 LIS 长度。

7 变体问题

7.1 最长非递减子序列（LNDS）

LNDS 将严格条件替换为非严格：允许相邻元素相等。它与 LIS 共享大部分结构，但关键差别在比较边界。

动态规划：比较条件从 \(a_j<a_i\) 改为 \(a_j\le a_i\)；
二分贪心：严格版的“下界”选择需要调整为对应非严格的边界规则。

7.2 最长上升子序列在二维（如坐标点的递增链）

当元素从一维数值扩展到二维坐标点 \((x,y)\)，常见目标是寻找嵌套关系：例如要求 \(x\) 也递增且 \(y\) 递增。直接做成二维偏序链问题后，可借助排序与一维化处理：

先按 \(x\) 排序；
再在相同 \(x\) 的情况下对 \(y\) 采取恰当排序方式，使得“链”不会错误地把相等 \(x\) 的点串起来；
最后对 \(y\) 的序列求（非）递减版本的 LIS。

7.2.1 嵌套条件的排序与转化思路

核心思想是把二维约束转换成对单个维度的单调要求。为了确保严格/非严格语义正确，需要处理同一 \(x\) 的并列情况：如果链要求 \(x\) 严格递增，则同 \(x\) 的点应当避免形成递增接力；因此通常对同 \(x\) 的 \(y\) 做反向排序或选择对应的严格/非严格变体。

7.3 最长摆动子序列（可作对照理解）

摆动子序列（wiggle subsequence）强调“方向交替”：相邻差值在符号上交替（正负轮换），而不一定要求整体单调上升。它与 LIS 的关系在于：两者都可用“动态规划 + 局部状态”的思路得到高效解，但状态定义不同。摆动子序列常用于对照理解“递增”这种局部约束如何改变算法细节。

7.4 允许间隔或代价约束的“带权”扩展

若递增不再只与数值大小有关，还可能涉及：

位置间隔限制（例如元素下标必须相距至少某个值）；
代价权重（例如选择某元素带来收益/消耗，并最大化总收益而不是长度）；

则可把 LIS 扩展为带权的最长链或带约束的动态规划问题。此类扩展通常需要更复杂的状态或数据结构（例如树状数组/线段树在特定条件下支持快速转移），但“可传递的最优子结构”仍是共同的精神内核。

8 参考与进一步阅读（面向学习路线）

8.1 从 O(n^2) 到 O(n log n) 的学习路径

学习建议从清晰的 \(O(n^2)\) 动态规划入手，掌握：

\(dp[i]\) 的含义；
如何记录前驱恢复方案；
严格/非严格对比较条件的影响。

随后再学习二分贪心，通过理解 tails 的含义与边界规则，把状态压缩到“最小结尾代表”，从而获得 \(O(n\log n)\) 的效率。

8.2 耐心排序与二分细节的练习清单

可通过以下练习巩固关键点：

大量重复元素下严格/非严格版本的差异；
手工模拟 tails 更新过程；
记录 tailsIndex 与回溯 pre 的一致性验证。

训练重点应放在二分边界与“pos 的含义”是否一致，而不是只看结论。

8.3 组合与理论视角的补充材料

若希望从更抽象的角度建立信心，可补充：

poset（偏序集）中的链与相关结构；
Dilworth 定理及其与链/反链的对偶直觉；
耐心排序与偏序理论的联系如何解释算法正确性。

这些材料更偏理论，但能帮助理解为何某些实现技巧并非“玄学”，而是来自结构上的一致性。