最长递增子序列线性 DP 的「三板斧」“给你一个数组找出里面最长的、越来越长的序列。注意不用连续只要相对顺序对就行。”这是 LeetCode 第 300 题——最长递增子序列Longest Increasing Subsequence简称 LIS。面试 DP 必考题但很多人卡在同一个地方dp[i]到底表示什么搞懂这道题你就掌握了线性 DP 最核心的三板斧。先举个栗子到底在问什么输入nums [10, 9, 2, 5, 3, 7, 101, 18] 输出4解释最长的递增子序列是[2, 3, 7, 101]长度为 4。注意几个坑子序列 ≠ 子数组子数组必须连续子序列可以跳着取严格递增不能相等[2, 2]不算递增相对顺序不能变101在18前面所以不能取[..., 18, 101]核心直觉为什么这道题是 DP假设你已经知道了以第 5 个元素结尾的最长递增子序列长度那以第 6 个元素结尾的答案能不能用它推出来能这就是 DP 的信号后面的答案可以由前面的答案推导出来。五步法推导从零到完整代码第一步定义状态最关键dp[i] 以nums[i]结尾的「最长递增子序列」的长度注意不是「前 i 个元素中最长的」而是必须以第 i 个元素结尾的。为什么这样定义因为以nums[i]结尾时前面那个元素一定比它小这样才能递推。nums: [10, 9, 2, 5, 3, 7, 101, 18] dp[i]: [ ?, ?, ?, ?, ?, ?, ?, ? ]第二步状态转移方程假设现在算dp[i]也就是以nums[i]结尾的最长递增子序列。它可以从哪里转移过来从所有比它小的元素转移过来如果 nums[j] nums[i]其中 j i 那么 dp[i] 至少可以是 dp[j] 1在所有满足条件的j中取最大值dp[i] max(dp[j] 1)其中0 j i且nums[j] nums[i]如果前面没有比它小的dp[i]只能是 1就自己一个。用图来理解nums: [10, 9, 2, 5, 3, 7, 101, 18] ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ dp: [ 1, 1, 1, 2, 2, 3, 4, 4] 解释 dp[3]以 5 结尾 - nums[0]10 5不行 - nums[1]9 5不行 - nums[2]2 5可以dp[2]1 2 - 所以 dp[3] 2对应序列 [2, 5] 解释 dp[6]以 101 结尾 - nums[2]2 101, dp[2]1 2 - nums[3]5 101, dp[3]1 3 - nums[4]3 101, dp[4]1 3 - nums[5]7 101, dp[5]1 4 ← 最大 - 所以 dp[6] 4对应序列 [2, 5, 7, 101] 或 [2, 3, 7, 101]第三步初始化每个元素自己就能构成长度为 1 的递增子序列dp[i] 1对所有 i第四步遍历顺序dp[i]依赖前面所有dp[j]j i所以外层从左到右遍历 i内层遍历 i 之前的所有 jfor(inti0;in;i){for(intj0;ji;j){// 计算 dp[i]}}第五步验证填表以nums [10, 9, 2, 5, 3, 7, 101, 18]为例inums[i]前面比它小的元素dp[i]对应的序列010无1[10]19无1[9]22无1[2]352 (j2, dp1)2[2, 5]432 (j2, dp1)2[2, 3]572(j2, dp1), 5(j3, dp2), 3(j4, dp2)3[2, 5, 7] 或 [2, 3, 7]61012,5,3,7 (最大的是 j5, dp3)4[2, 3, 7, 101]7182,5,3,7 (最大的是 j5, dp3)4[2, 3, 7, 18]最终答案max(dp) 4✅完整代码JavaclassSolution{publicintlengthOfLIS(int[]nums){intnnums.length;// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度int[]dpnewint[n];// 初始化每个元素至少可以单独成序列长度为 1Arrays.fill(dp,1);// 遍历每个位置 ifor(inti0;in;i){// 看 i 之前的所有位置 jfor(intj0;ji;j){// 只有当 nums[j] nums[i] 时才能接在后面形成递增if(nums[j]nums[i]){// 尝试更新以 i 结尾的最长长度dp[i]Math.max(dp[i],dp[j]1);}}}// 答案不一定是 dp[n-1]要取整个 dp 数组的最大值intresult0;for(intlen:dp){resultMath.max(result,len);}returnresult;}}时间复杂度O(n^2) —— 两重循环每个 i 都要看前面所有 j空间复杂度O(n) —— 一维 dp 数组进阶O(n log n) 解法二分查找如果面试官追问能不能优化到 O(n log n)你可以祭出这个技巧核心思想维护一个数组tails其中tails[k]表示长度为 k1 的递增子序列中末尾元素的最小值。为什么只关心最小值因为末尾越小后面越容易被接上。nums: [10, 9, 2, 5, 3, 7, 101, 18] 处理 10: tails [10] 处理 9: 9 比 10 小替换 → tails [9] 处理 2: 2 比 9 小替换 → tails [2] 处理 5: 5 比 2 大接在后面 → tails [2, 5] 处理 3: 3 在 2 和 5 之间替换 5 → tails [2, 3] 处理 7: 7 比 3 大接在后面 → tails [2, 3, 7] 处理 101: 接在后面 → tails [2, 3, 7, 101] 处理 18: 18 在 7 和 101 之间替换 101 → tails [2, 3, 7, 18] 最终 tails 的长度 4就是答案为什么可以用二分因为tails数组一定是递增的所以可以用二分查找来确定每个数该放的位置。classSolution{publicintlengthOfLIS(int[]nums){// tails[k] 表示长度为 k1 的递增子序列的最小末尾值int[]tailsnewint[nums.length];intsize0;// 当前 tails 的有效长度for(intnum:nums){// 二分查找num 应该放在 tails 的哪个位置intleft0,rightsize;while(leftright){intmidleft(right-left)/2;if(tails[mid]num){leftmid1;// num 更大去右边找}else{rightmid;// num 更小或相等去左边或替换当前}}// left 就是 num 该放的位置tails[left]num;// 如果放到末尾说明序列变长了if(leftsize){size;}}returnsize;}}时间复杂度O(n log n) —— 每个元素做一次二分空间复杂度O(n) —— tails 数组两种解法对比解法时间复杂度核心思想面试建议DPO(n^2)dp[i]表示以 i 结尾的最长长度先写这个稳妥二分O(nlogn)O(n \log n)O(nlogn)维护最小末尾数组 二分进阶加分项面试时先写 DP 版本然后主动说这道题还有O(nlogn)O(n \log n)O(nlogn)的优化解法展示你的深度。一句话总结dp[i] 以 nums[i] 结尾的最长递增子序列长度 dp[i] max(dp[j] 1) 对于所有 j i 且 nums[j] nums[i]这道题是线性 DP 的「试金石」状态定义是「以 i 结尾」而不是「前 i 个的最大值」转移时不是只看 i-1而是看前面所有比它小的答案是整个 dp 数组的最大值不是最后一个搞懂了这三点最长递增子序列就彻底毕业了。收藏这篇下次遇到 LIS 变形题比如最长递减子序列、最长摆动子序列照样秒杀。欢迎在评论区交流你的 DP 学习心得或者留下你想了解的算法题下期安排
最长递增子序列线性 DP 的「三板斧」“给你一个数组找出里面最长的、越来越长的序列。注意不用连续只要相对顺序对就行。”这是 LeetCode 第 300 题——最长递增子序列Longest Increasing Subsequence简称 LIS。面试 DP 必考题但很多人卡在同一个地方dp[i]到底表示什么搞懂这道题你就掌握了线性 DP 最核心的三板斧。先举个栗子到底在问什么输入nums [10, 9, 2, 5, 3, 7, 101, 18] 输出4解释最长的递增子序列是[2, 3, 7, 101]长度为 4。注意几个坑子序列 ≠ 子数组子数组必须连续子序列可以跳着取严格递增不能相等[2, 2]不算递增相对顺序不能变101在18前面所以不能取[..., 18, 101]核心直觉为什么这道题是 DP假设你已经知道了以第 5 个元素结尾的最长递增子序列长度那以第 6 个元素结尾的答案能不能用它推出来能这就是 DP 的信号后面的答案可以由前面的答案推导出来。五步法推导从零到完整代码第一步定义状态最关键dp[i] 以nums[i]结尾的「最长递增子序列」的长度注意不是「前 i 个元素中最长的」而是必须以第 i 个元素结尾的。为什么这样定义因为以nums[i]结尾时前面那个元素一定比它小这样才能递推。nums: [10, 9, 2, 5, 3, 7, 101, 18] dp[i]: [ ?, ?, ?, ?, ?, ?, ?, ? ]第二步状态转移方程假设现在算dp[i]也就是以nums[i]结尾的最长递增子序列。它可以从哪里转移过来从所有比它小的元素转移过来如果 nums[j] nums[i]其中 j i 那么 dp[i] 至少可以是 dp[j] 1在所有满足条件的j中取最大值dp[i] max(dp[j] 1)其中0 j i且nums[j] nums[i]如果前面没有比它小的dp[i]只能是 1就自己一个。用图来理解nums: [10, 9, 2, 5, 3, 7, 101, 18] ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ dp: [ 1, 1, 1, 2, 2, 3, 4, 4] 解释 dp[3]以 5 结尾 - nums[0]10 5不行 - nums[1]9 5不行 - nums[2]2 5可以dp[2]1 2 - 所以 dp[3] 2对应序列 [2, 5] 解释 dp[6]以 101 结尾 - nums[2]2 101, dp[2]1 2 - nums[3]5 101, dp[3]1 3 - nums[4]3 101, dp[4]1 3 - nums[5]7 101, dp[5]1 4 ← 最大 - 所以 dp[6] 4对应序列 [2, 5, 7, 101] 或 [2, 3, 7, 101]第三步初始化每个元素自己就能构成长度为 1 的递增子序列dp[i] 1对所有 i第四步遍历顺序dp[i]依赖前面所有dp[j]j i所以外层从左到右遍历 i内层遍历 i 之前的所有 jfor(inti0;in;i){for(intj0;ji;j){// 计算 dp[i]}}第五步验证填表以nums [10, 9, 2, 5, 3, 7, 101, 18]为例inums[i]前面比它小的元素dp[i]对应的序列010无1[10]19无1[9]22无1[2]352 (j2, dp1)2[2, 5]432 (j2, dp1)2[2, 3]572(j2, dp1), 5(j3, dp2), 3(j4, dp2)3[2, 5, 7] 或 [2, 3, 7]61012,5,3,7 (最大的是 j5, dp3)4[2, 3, 7, 101]7182,5,3,7 (最大的是 j5, dp3)4[2, 3, 7, 18]最终答案max(dp) 4✅完整代码JavaclassSolution{publicintlengthOfLIS(int[]nums){intnnums.length;// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度int[]dpnewint[n];// 初始化每个元素至少可以单独成序列长度为 1Arrays.fill(dp,1);// 遍历每个位置 ifor(inti0;in;i){// 看 i 之前的所有位置 jfor(intj0;ji;j){// 只有当 nums[j] nums[i] 时才能接在后面形成递增if(nums[j]nums[i]){// 尝试更新以 i 结尾的最长长度dp[i]Math.max(dp[i],dp[j]1);}}}// 答案不一定是 dp[n-1]要取整个 dp 数组的最大值intresult0;for(intlen:dp){resultMath.max(result,len);}returnresult;}}时间复杂度O(n^2) —— 两重循环每个 i 都要看前面所有 j空间复杂度O(n) —— 一维 dp 数组进阶O(n log n) 解法二分查找如果面试官追问能不能优化到 O(n log n)你可以祭出这个技巧核心思想维护一个数组tails其中tails[k]表示长度为 k1 的递增子序列中末尾元素的最小值。为什么只关心最小值因为末尾越小后面越容易被接上。nums: [10, 9, 2, 5, 3, 7, 101, 18] 处理 10: tails [10] 处理 9: 9 比 10 小替换 → tails [9] 处理 2: 2 比 9 小替换 → tails [2] 处理 5: 5 比 2 大接在后面 → tails [2, 5] 处理 3: 3 在 2 和 5 之间替换 5 → tails [2, 3] 处理 7: 7 比 3 大接在后面 → tails [2, 3, 7] 处理 101: 接在后面 → tails [2, 3, 7, 101] 处理 18: 18 在 7 和 101 之间替换 101 → tails [2, 3, 7, 18] 最终 tails 的长度 4就是答案为什么可以用二分因为tails数组一定是递增的所以可以用二分查找来确定每个数该放的位置。classSolution{publicintlengthOfLIS(int[]nums){// tails[k] 表示长度为 k1 的递增子序列的最小末尾值int[]tailsnewint[nums.length];intsize0;// 当前 tails 的有效长度for(intnum:nums){// 二分查找num 应该放在 tails 的哪个位置intleft0,rightsize;while(leftright){intmidleft(right-left)/2;if(tails[mid]num){leftmid1;// num 更大去右边找}else{rightmid;// num 更小或相等去左边或替换当前}}// left 就是 num 该放的位置tails[left]num;// 如果放到末尾说明序列变长了if(leftsize){size;}}returnsize;}}时间复杂度O(n log n) —— 每个元素做一次二分空间复杂度O(n) —— tails 数组两种解法对比解法时间复杂度核心思想面试建议DPO(n^2)dp[i]表示以 i 结尾的最长长度先写这个稳妥二分O(nlogn)O(n \log n)O(nlogn)维护最小末尾数组 二分进阶加分项面试时先写 DP 版本然后主动说这道题还有O(nlogn)O(n \log n)O(nlogn)的优化解法展示你的深度。一句话总结dp[i] 以 nums[i] 结尾的最长递增子序列长度 dp[i] max(dp[j] 1) 对于所有 j i 且 nums[j] nums[i]这道题是线性 DP 的「试金石」状态定义是「以 i 结尾」而不是「前 i 个的最大值」转移时不是只看 i-1而是看前面所有比它小的答案是整个 dp 数组的最大值不是最后一个搞懂了这三点最长递增子序列就彻底毕业了。收藏这篇下次遇到 LIS 变形题比如最长递减子序列、最长摆动子序列照样秒杀。欢迎在评论区交流你的 DP 学习心得或者留下你想了解的算法题下期安排
