最长递增子序列

功能说明

longestIncreasingSubsequence 返回数组中最长递增子序列的长度、具体值与原始下标。strict 为真时要求严格递增，为假时允许相等元素。算法使用耐心排序与二分查找，将动态规划的 O(n²) 降为 O(n log n)，适合版本序列分析、日志趋势、排期依赖和任意可比较数值序列。

关键代码

tails 保存每个长度对应的最小结尾值，tailIndices 记录该结尾在原数组中的位置，previous 为每个元素记录前驱下标。处理新值时用二分找到第一个不小于它的位置，严格模式比较小于，非严格模式比较小于等于，从而决定替换位置。更新 tails 后写入前驱，最后从最长长度的结尾回溯并反转，得到完整下标链。

使用注意

tails 数组本身不是最终子序列，只有通过 previous 回溯才能得到真实下标，直接返回 tails 是常见错误。算法对 NaN 会拒绝，因为比较不成立。非严格模式允许相等值连续出现，但返回的是其中一条合法子序列。输入不会被修改。若只需要长度，可以省略前驱数组以节省内存。

验证方式

测试空数组、单元素、严格递增、严格递减、全部相等与含负数序列。用经典序列 10,9,2,5,3,7,101,18 验证长度为四，并检查返回下标对应的值确实递增。对比暴力动态规划在随机小数组上的长度，覆盖 strict 为 false 时相等元素可连续选择的行为，并测试 NaN、Infinity 与字符串元素会抛错。

代码示例

export interface LisResult {
  length: number;
  sequence: number[];
  indices: number[];
}

export function longestIncreasingSubsequence(values: readonly number[], strict = true): LisResult {
  if (!values.every((value) => Number.isFinite(value))) {
    throw new TypeError("values must contain finite numbers");
  }
  const tails: number[] = [];
  const tailIndices: number[] = [];
  const previous = new Array<number>(values.length).fill(-1);
  for (let index = 0; index < values.length; index += 1) {
    const value = values[index]!;
    let low = 0;
    let high = tails.length;
    while (low < high) {
      const middle = (low + high) >> 1;
      const goesRight = strict ? tails[middle]! < value : tails[middle]! <= value;
      if (goesRight) low = middle + 1;
      else high = middle;
    }
    tails[low] = value;
    tailIndices[low] = index;
    previous[index] = low > 0 ? tailIndices[low - 1]! : -1;
  }
  const indices: number[] = [];
  let cursor = tailIndices.length > 0 ? tailIndices[tailIndices.length - 1]! : -1;
  while (cursor !== -1) {
    indices.push(cursor);
    cursor = previous[cursor]!;
  }
  indices.reverse();
  return {
    length: indices.length,
    sequence: indices.map((index) => values[index]!),
    indices,
  };
}