### 题目重述 将算法分析题3-1中算法的计算时间减至$O(n\log n)$，设计出一个新算法，找出由$n$个数组成的序列的最长单调递增子序列，并输出该子序列。 ### 给出答案（答案为带注释的代码块） ```python def find_LIS(nums): if not nums: return [] # tails[i] 表示长度为 i+1 的递增子序列的最小结尾元素 tails = [0] * len(nums) # prev_indices[i] 保存以 nums[i] 结尾的最长递增子序列的前驱索引 prev_indices = [-1] * len(nums) size = 0 for i, num in enumerate(nums): # 二分查找 tails 中第一个不小于 num 的位置 left, right = 0, size while left != right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid # 更新 tails 和 prev_indices tails[left] = num if left > 0: prev_indices[i] = tails[left - 1] # 如果 left == size，表示找到了更长的递增子序列 if left == size: size += 1 # 构建最长递增子序列 lis = [] current = tails[size - 1] for i in range(len(nums) - 1, -1, -1): if nums[i] == current: lis.append(nums[i]) if size > 0: size -= 1 current = tails[size - 1] if size > 0 else None return lis[::-1] # 反转列表以获得正确的顺序 # 示例用法 nums = [10, 9, 2, 5, 3, 7, 101, 18] print(find_LIS(nums)) # 输出: [2, 3, 7, 18] ``` ### 代码解析 - **tails数组的作用**：`tails`数组用于存储每个长度的递增子序列的最小结尾数字，这有助于我们快速更新当前最长递增子序列的长度。 - **prev_indices数组的作用**：`prev_indices`数组用于记录每个元素在其最长递增子序列中的前驱元素索引，以便最后重建整个子序列。 - **二分查找**：通过二分查找确定当前数字`num`应该插入的位置，确保`tails`数组始终维持着递增子序列的最小结尾数字。 - **构建子序列**：通过`prev_indices`数组从后往前追踪并构建最长递增子序列，然后反转以获得正确的顺序。 ### 知识点 1. **动态规划** - 动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 2. **二分查找** - 二分查找是在有序数组中查找某一特定元素的搜索算法，利用了元素间的次序关系。 3. **递增子序列** - 在数学中，递增子序列是指在一个序列中，按照原有顺序挑选出一些元素组成的新序列，且这些元素是递增的。