LeetCode-Book 精讲最长递增子序列LIS——从 O(N²) 动态规划到 O(NlogN) 二分优化【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文以 LeetCode-Book 仓库中《Krahets 笔面试精选 88 题》的「最长递增子序列」题解为主体系统讲解该题的两套经典解法O(N²) 的常规动态规划以及通过重新设计状态定义将复杂度降至 O(NlogN) 的动态规划 二分查找。读完本文你将掌握 LIS 问题「状态定义 → 转移方程 → 复杂度优化」的完整分析链路理解二分优化背后的数学直觉并能直接运行仓库中给出的 Python / Java 源码进行验证。一、题目概述什么是最长递增子序列「最长递增子序列」Longest Increasing SubsequenceLIS是动态规划领域的经典入门题目LeetCode 300 题也是《Krahets 笔面试精选 88 题》中的高频考点。题目要求给定一个无序整数数组nums找到其中最长严格递增子序列的长度。理解此题必须抓住两个关键点子序列 ≠ 子数组子序列不要求元素在原数组中连续只需保持相对顺序即可。例如[10, 9, 2, 5, 3, 7, 101, 18]中[2, 3, 7, 101]就是一个合法的递增子序列尽管它在原数组中并不连续。严格递增要求nums[i] nums[j]后一个元素严格大于前一个即不允许相等元素相邻构成递增关系。原题解文档位于 selected_coding_interview/docs/300. 最长递增子序列.md对应的可运行代码在 Python 源码 与 Java 源码 中下文将逐一展开。二、解法一动态规划O(N²)这是最直观、最符合 DP 学习路径的解法枚举每个元素作为「子序列结尾」的所有可能逐步累积出全局最优解。2.1 状态定义定义dp[i]为以nums[i]结尾的最长递增子序列的长度。注意这里的状态不是全局最长而是强制以第 i 个元素收尾这是后续转移能够成立的关键。2.2 转移方程设j ∈ [0, i)计算每个新的dp[i]时遍历[0, i)区间内的所有元素逐一判断当nums[i] nums[j]时nums[i]可以接在nums[j]之后题目要求严格递增此时以nums[i]结尾的子序列长度为dp[j] 1当nums[i] nums[j]时nums[i]无法接在nums[j]之后该情况不构成递增子序列跳过。对上述所有第 1 种情况求最大值即为dp[i]的最终取值。实现时只需在遍历j的每一轮执行dp[i] max(dp[i], dp[j] 1) for j in [0, i)2.3 初始状态与返回值初始状态dp[i]所有元素初始化为1。含义是每个元素自身至少可以单独构成一个长度为 1 的递增子序列。返回值返回dp列表的最大值即全局最长递增子序列的长度。2.4 复杂度分析时间复杂度 O(N²)遍历计算dp列表需 O(N)计算每个dp[i]又需遍历[0, i)区间 O(N)总复杂度 O(N²)。空间复杂度 O(N)dp列表占用线性大小的额外空间。2.5 代码实现仓库中的 Python 与 Java 实现与原文档一致可直接运行验证# Dynamic programming. class Solution: def lengthOfLIS(self, nums: List[int]) - int: if not nums: return 0 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) return max(dp)// Dynamic programming. class Solution { public int lengthOfLIS(int[] nums) { if(nums.length 0) return 0; int[] dp new int[nums.length]; int res 0; Arrays.fill(dp, 1); for(int i 0; i nums.length; i) { for(int j 0; j i; j) { if(nums[j] nums[i]) dp[i] Math.max(dp[i], dp[j] 1); } res Math.max(res, dp[i]); } return res; } }对应仓库文件Python 解法一、Java 解法一。仓库为两种解法都附带了完整的测试驱动代码# Test Case 与main方法测试输入为[1, 2, 3, 4, 5]期望输出5可直接运行查看结果。2.6 手推示例以nums [10, 9, 2, 5, 3, 7, 101, 18]为例逐步推演inums[i]dp[i] 推导过程dp[i]010无 j 可比较保持初始值1199 10不成立无转移122前两个元素均大于 2无转移1352 5dp[2]1 22432 3dp[2]1 225727(dp2)、57(dp3)、37(dp3)46101前面所有元素均小于 101取最大dp157181018(dp2)、218(dp2)、518(dp3)、318(dp3)、718(dp4)5最终max(dp) 5即最长递增子序列[2, 5, 7, 101]或[2, 3, 7, 18]的长度。三、解法二动态规划 二分查找O(NlogN)解法一在N很大时会超时因此需要优化。优化思路不能简单套模板而要重新审视状态定义本身。3.1 优化切入点复杂度从何而来回顾解法一的两层循环外层遍历计算所有dp值需要 O(N)这是无法避免的内层为计算每个dp[k]需要线性遍历[0, k)区间共 O(N)。那么关键问题就变成了能否重新设计状态定义使得用于转移的辅助列表天然有序从而把内层遍历从 O(N) 降为 O(logN)3.2 新的状态定义tails 列表维护一个列表tails其中tails[k]表示长度为k1的递增子序列的尾部元素值。例如序列[1, 4, 6]长度为 1、2、3 的子序列尾部元素值分别为tails [1, 4, 6]。tails并不直接等于某个具体的递增子序列它只记录各类长度的子序列在最优选择下的尾部最小值其长度res即当前已知的最长递增子序列长度。3.3 贪心直觉尾部元素越小越好为什么遍历时要不断更新、始终保持每个尾部元素值最小原因很简单设常量数字N和随机数字x当N越小时N x的概率越大。例如N 0一定比N 1000更可能满足N x。对应到算法中在遍历计算每个tails[k]时不断更新长度为[1, k]的子序列尾部元素值始终保持每个尾部元素值最小。例如序列[1, 5, 3]遍历到元素5时长度为 2 的子序列尾部元素值为5此时tails [1, 5]遍历到元素3时应把尾部元素值更新为3tails [1, 3]因为3比5遇到比它更大的数字的几率更大更有利于后续接出更长的序列。3.4 tails 必然严格递增反证法证明这是二分查找能够应用的前提也是本解法最精妙的推理命题在尽量使每个子序列尾部元素值最小的前提下子序列越长其尾部元素值一定更大即tails严格递增。反证法假设k i时存在tails[k] tails[i]意味着较短的子序列尾部元素值不小于较长的子序列尾部元素值。但从长度为i的子序列尾部倒序删除i - 1个元素剩下的就是长度为k的子序列设其尾部元素值为v则一定有v tails[i]长度为 k 的子序列尾部元素值必然更小这与tails[k] tails[i]矛盾。因此假设不成立tails必然严格递增。既然tails严格递增每轮计算时就可以用二分查找快速定位需要更新的尾部元素索引。3.5 算法流程状态定义tails[k]表示长度为k1的递增子序列的尾部元素值。转移方程设res为tails当前长度即当前已知的最长递增子序列长度每轮遍历nums[k]时在[0, res)区间二分查找nums[k]的大小分界点区间中存在tails[i] nums[k]将第一个满足tails[i] nums[k]的元素更新为nums[k]即tails[i] nums[k]因为更小的尾部元素后更可能接上更大的数字区间中不存在tails[i] nums[k]说明nums[k]可以接在目前所有长度的子序列之后最优策略是接到最长序列长度为res后面形成长度为res 1的新子序列。初始状态tails列表所有值初始化为0Java 中 int 数组默认即全 0。返回值返回res即最长递增子序列的长度。3.6 复杂度分析时间复杂度 O(NlogN)遍历nums需 O(N)每个nums[i]的二分查找需 O(logN)。空间复杂度 O(N)tails列表占用线性大小的额外空间。3.7 代码实现# Dynamic programming Dichotomy. class Solution: def lengthOfLIS(self, nums: [int]) - int: tails, res [0] * len(nums), 0 for num in nums: i, j 0, res while i j: m (i j) // 2 if tails[m] num: i m 1 # 如果要求非严格递增将此行 改为 即可。 else: j m tails[i] num if j res: res 1 return res// Dynamic programming Dichotomy. class Solution { public int lengthOfLIS(int[] nums) { int[] tails new int[nums.length]; int res 0; for(int num : nums) { int i 0, j res; while(i j) { int m (i j) / 2; if(tails[m] num) i m 1; else j m; } tails[i] num; if(res j) res; } return res; } }对应仓库文件Python 解法二、Java 解法二。3.8 二分过程手推仍以nums [10, 9, 2, 5, 3, 7, 101, 18]为例遍历元素tails 更新前后res10[10]19[9]9 10更新尾部12[2]2 9更新尾部15[2, 5]5 2追加23[2, 3]3 5二分定位替换27[2, 3, 7]追加3101[2, 3, 7, 101]追加418[2, 3, 7, 18]18 101二分定位替换4最终res 4。注意此示例中解法一与解法二结果一致均为 4说明两种算法在求长度上等价需要强调的是tails本身并不对应真实的最长递增子序列它只是记录了各长度下最有利的尾部值。四、两种解法对比与实战选择维度解法一动态规划解法二动态规划 二分时间复杂度O(N²)O(NlogN)空间复杂度O(N)O(N)状态含义dp[i]以nums[i]结尾的 LIS 长度tails[k]长度为 k1 的子序列尾部最小元素转移手段线性遍历[0, i)取最大值二分查找定位替换点代码量较少直观易写稍复杂需要理解贪心与二分适用场景面试中优先给出、易于讲解大数据量下必须使用实战建议面试时先流畅给出 O(N²) 动态规划解法包含状态定义、转移方程、初始状态、返回值四要素再主动提出可以用贪心 二分优化到 O(NlogN)并讲清tails严格递增的反证法证明——这正是本题区分度最高的考察点。原文档也按此顺序组织两种解法从 题解文档 可直接对照学习。五、进阶拓展5.1 非严格递增变体只改一行两道代码注释中都明确提示了变体改法如果要求非严格递增将此行改为即可。解法一中if nums[j] nums[i]:改为if nums[j] nums[i]:解法二中if tails[m] num: i m 1改为if tails[m] num: i m 1。原因在于非严格递增允许相等元素相接二分查找时相等值不应视为需要替换的更大元素而是应继续向右搜索以接在等值元素之后从而正确统计长度。5.2 如何重构出具体的最长递增子序列题目只要求返回长度但面试中常被追问能否输出具体序列。可以推断有两种常见扩展思路回溯法配合 O(N²) DP在计算dp[i]时记录pre[i] j转移来源下标最后从dp最大值位置沿pre链回溯即可还原序列贪心二分法配合 O(NlogN) 解法额外维护idx数组记录每个tails元素在原数组中的下标并用pre数组记录更新时的前驱下标同样可还原出一个合法的最长递增子序列。5.3 仓库内相关 DP 题目联动LIS 属于线性 DP / 序列 DP的经典范式仓库中还收录了多道可对比练习的动态规划题目适合串联复习最大子数组和剑指 Offer 42 与 LCR 161同样是定义以 i 结尾的 DP但转移只依赖前一项复杂度可做到 O(N)打家劫舍198. 打家劫舍与打家劫舍 II213. 打家劫舍 II掌握状态机 DP 环形处理整数拆分343. 整数拆分理解枚举切割点式的区间转移最小路径和64. 最小路径和二维 DP 的入门代表。六、小结「最长递增子序列」一题完整覆盖了动态规划的四个标准步骤状态定义、转移方程、初始状态、返回值又通过重新设计状态引入了贪心 二分这一高频优化技巧是训练面试算法思维的极佳载体。建议在 LeetCode-Book 仓库中对照 题解文档 通读推理过程再运行仓库中的 Python 与 Java 源码验证结果最后尝试自行推导非严格递增变体与序列重构做到举一反三。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考