- 正确答案：最长递增子序列（Longest Increasing Subsequence，LIS）是指在一个给定数组中，找到一个最长的子序列（元素在原数组中下标严格递增，不要求连续），使得该子序列中每个元素严格大于前一个元素。其长度即为LIS长度；若需输出具体子序列，还需记录路径。经典解法有两种： 1. 动态规划（DP）解法：时间复杂度 O(n²)，空间复杂度 O(n)，可还原路径； 2. 贪心 + 二分搜索解法：时间复杂度 O(n log n)，空间复杂度 O(n)，仅得长度；若需构造实际子序列，需额外维护 parent 数组或反向回溯技巧。以输入 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例，LIS 长度为 4，一个合法 LIS 是 [2, 3, 7, 18] 或 [2, 5, 7, 101]。 - 解答思路：第一步：明确“子序列” vs “子数组”——子序列不要求连续，只保留下标递增顺序；第二步：理解“递增”是严格递增（a[i] < a[j]，i < j），非非递减；第三步：考虑状态定义： - DP 方法：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度；状态转移：dp[i] = max{ dp[j] + 1 }，其中 j ∈ [0, i−1] 且 nums[j] < nums[i]；初始 dp[i] = 1；最终答案为 max(dp[0..n−1])。 - 贪心+二分方法：维护一个辅助数组 tail，其中 tail[len] 表示长度为 len+1 的所有 LIS 中，末尾元素的最小可能值；遍历 nums[i] 时，用二分查找在 tail[0..len] 中找到第一个 ≥ nums[i] 的位置 pos，令 tail[pos] = nums[i]；若 pos == len，则 len++（说明可延长当前最长长度）；最终 len 即为 LIS 长度。注意：tail 数组本身不构成真实子序列，但保证了长度正确性；其单调性（严格递增）是贪心合法性的核心保障。 - 深度知识讲解： 1. 底层原理——为什么 tail 数组单调？ - 关键性质：对任意长度 L，我们只保留能构成长度为 L 的 LIS 的最小末尾值。更小的末尾值为后续元素提供更多扩展机会（即更大概率满足 nums[i] > tail[L−1]）。因此 tail 数组天然严格递增（若 tail[i] >= tail[j] 且 i= x 的位置 left, right = 0, length while left < right: mid = (left + right) // 2 if tail[mid] < x: left = mid + 1 else: right = mid tail[left] = x if left == length: length += 1 return length # 测试 print(length_of_LIS([10,9,2,5,3,7,101,18])) # 输出 4 - 进阶：如何还原一条具体的 LIS？需额外维护： - parent[i]：记录 nums[i] 在 LIS 中的前驱索引（仅对 DP 法自然支持）； - 或在贪心法中，对每个 nums[i] 记录其插入 tail 的位置 pos，然后逆向扫描：从最后一个被更新的 pos = length−1 开始，在原始数组中从右往左找满足 nums[i] < nums[j] 且 pos[i] == pos−1 的 j —— 实现较繁琐，面试中若被问及，建议优先使用 DP 法还原。 DP 还原路径伪代码： dp = [1] * n parent = [-1] * n for i in range(n): for j in range(i): if nums[j] < nums[i] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 parent[i] = j # 找 dp 最大值对应索引 idx lis = [] while idx != -1: lis.append(nums[idx]) idx = parent[idx] lis.reverse() - 延伸考点： - 与 patience sorting（纸牌游戏类比）的关系：LIS 长度等于将数组按规则分堆所需的最少堆数（每堆降序，新数只能放于顶部比它大的堆顶，否则新建堆），而 tail 数组即各堆顶元素； - Dilworth 定理视角：偏序集（i < j ∧ nums[i] < nums[j]）中，最长链长 = 最小反链划分，LIS 长度 = 最少的“递减子序列”划分数； - 实际应用：生物信息学（DNA序列比对）、编译器优化（指令调度）、数据压缩（增量编码）等。综上，手撕 LIS 不仅考察算法实现，更检验对动态规划状态设计、贪心正确性证明、二分搜索变形、以及数据结构抽象能力（tail 数组的隐式单调栈性质）的综合理解。

腾讯CDG大模型一面-日常实习

全站热榜

创作者周榜