介绍

在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论（英语：random matrix theory）、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求$O(nlogn)$ 的时间复杂度，这里 n 表示输入序列的规模。

实现

JavaScript

/**
 * A Dynamic Programming based solution for calculating Longest Increasing Subsequence
 * https://en.wikipedia.org/wiki/Longest_increasing_subsequence
 */

// Return the length of the Longest Increasing Subsequence, given array x
function longestIncreasingSubsequence (x) {
  const length = x.length
  const dp = Array(length).fill(1)

  let res = 1

  for (let i = 0; i < length; i++) {
    for (let j = 0; j < i; j++) {
      if (x[i] > x[j]) {
        dp[i] = Math.max(dp[i], 1 + dp[j])
        if (dp[i] > res) res = dp[i]
      }
    }
  }

  return res
}

扩展

二分查找解决最长递增子序列问题。

思路：

原始数组为 A, 建立一个辅助数组 B, 变量 end 用来记录 B 数组末尾元素的下标。遍历 A 中的所有的元素 x = A [i]：

• 如果 x > B 的末尾元素，则将 x 追加到 B 的末尾，end+=1
• 如果 x <B 的末尾元素，则利用二分查找，寻找 B 中第一个大于 x 的元素，并用 x 进行替换 e.g. x= 4 B=[1,3,5,6] ==> B=[1,3,4,6]

遍历结束之后，B 的长度则为最长递增子序列的长度。

Python：

def get_lis_length(arr):
  temp = [arr[0]]
  end = 0

  for i in range(1, len(arr)):
    if arr[i] > temp[end]:
      end += 1
      temp.append(arr[i])
    else :
      pos = binary_search(temp,0, len(temp), arr[i])
      temp[pos] = arr[i]
  return end + 1

def binary_search(arr, start, end, value):
  l = start
  r = end-1
  while l <= r:
    m = (l + r) // 2
    if arr[m] == value:
      return m
    elif arr[m] < value:
      l = m + 1
    else:
      r = m - 1
  return l

# arr = [2, 1, 5, 3, 6, 4, 8, 9, 7]
# print(get_lis_length(arr))

• // 即 floordiv (a, b)。参见 operator --- 标准运算符替代函数 — Python 3.10.8 文档 (opens new window)。

思路

在循环中找到正序的子序列，此时子序列的长度应该继续增加而不能减少。因此通过减小序列递增值（替换较大值）以降低序列长度增加的成本。

参考

• Longest increasing subsequence - Wikiwand (opens new window)
• 最长递增子序列 - Wikiwand (opens new window)
• fucking-algorithm / 动态规划设计：最长递增子序列.md at master・labuladong/fucking-algorithm (opens new window)
• 最长递增子序列 - 知乎 (opens new window)