longestIncreasingSubsequence

查找数组中最长的严格递增子序列,使用动态规划和二分查找优化算法实现。

输入数组

待处理数组 (用逗号分隔)

执行过程

步骤 1 / 40

开始计算最长递增子序列，初始化tails数组为空

原始数组

0

10

1

9

2

2

3

5

4

3

5

7

6

101

7

18

速度:慢速正常快速超快

当前处理

查找范围

中间位置

已更新

LIS序列

算法说明

最长递增子序列使用动态规划+二分查找优化，tails[i]表示长度为i+1的递增子序列的最小尾部元素。时间复杂度O(n log n)。

函数签名

function longestIncreasingSubsequence(
  nums: number[],
  includeDp?: boolean
): LISResult

interface LISResult {
  length: number
  sequence: number[]
  dp?: number[]
}

参数

参数名	类型	必填	说明
nums	number[]	是	数字数组
includeDp	boolean	否	是否在结果中包含DP数组(用于调试),默认false

返回值

类型	说明
LISResult	LIS结果对象

LISResult 结构:

属性	类型	说明
length	number	最长递增子序列的长度
sequence	number[]	最长递增子序列数组
dp	number[]	DP数组(可选,仅当includeDp为true时)

工作原理

1. 初始化辅助数组:
   • tails[i] 表示长度为 i+1 的递增子序列的最小尾部元素
   • parent[i] 记录元素在LIS中的前驱索引
   • tailIndices[i] 记录 tails[i] 对应的元素索引
2. 遍历数组: 对每个元素,使用二分查找在 tails 数组中找到合适的位置
3. 更新辅助数组: 更新 tails 数组并记录父节点关系
4. 回溯构建序列: 从最后一个元素开始,通过 parent 数组回溯构建完整的LIS
5. 返回结果: 返回LIS长度和序列数组

时间复杂度: O(n log n),其中 n 是数组长度
空间复杂度: O(n)

优化说明: 相比传统的 O(n²) 动态规划算法,本实现通过二分查找优化到 O(n log n)