Longest Increasing Subsequence

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,
  };
}