最长递增子序列

这是一道经典的算法题。

在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。解决最长递增子序列问题的算法最低要求O(n log n)的时间复杂度，这里n表示输入序列的规模。

多数解法是使用动态规划的思想，算法的时间复杂度是 O(n2)，而 Vue.js 内部使用的是“贪心 + 二分查找”的算法，贪心算法的时间复杂度是 O(n)，二分查找的时间复杂度是 O(logn)，所以它的总时间复杂度是 O(nlogn)。

例子

对于以下的原始序列

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
最长递增子序列为

0, 2, 6, 9, 11, 15.
值得注意的是原始序列的最长递增子序列并不一定唯一，对于该原始序列，实际上还有以下三个最长递增子序列

0, 4, 6, 9, 11, 15
0, 4, 6, 9, 13, 15
0, 2, 6, 9, 13, 15
复制代码

下面概述的算法使用数组和二分查找算法有效地解决了最长递增子序列问题。它依次处理序列元素，保存当前找到的最长的递增子序列，比如: [X[0]，X [1]]。在处理X[i]之后，算法会将值存储在两个数组中：

M[j] — 存储值最小的X [k]的索引k，以使在范围k≤i上，以X [k]结尾的长度为j的子序列增加。注意：j ≤ (i+1)，因为j≥1表示递增子序列的长度，而k≥0表示其终止的索引。
P[k] — 将X [k]的前任索引存储在以X [k]结尾的最长递增子序列中。

另外，该算法还存储了一个变量L，该变量L表示到目前为止找到的最长的递增子序列的长度。下面的算法使用基于零的编号，为了清楚起见，M用M [0]填充，而M [0]未使用，因此M [j]对应于长度j的子序列。实际的实现可以跳过M [0]并相应地调整索引。

请注意，在算法的任何时候，序列

X[M[1]], X[M[2]], …, X[M[L]]
是递增的。因为，如果长度j≥2的子序列以X [M [j]]结尾，则长度j-1的子序列以较小的值结尾：即以X [P [M]结尾的子序列 [j]]。因此，我们可以使用二分查找在O(log n)时间内完成搜索。

伪代码如下：

P = array of length N
M = array of length N + 1

L = 0
for i in range 0 to N-1:
    // Binary search for the largest positive j ≤ L
    // such that X[M[j]] <= X[i]
    lo = 1
    hi = L
    while lo ≤ hi:
        mid = ceil((lo+hi)/2)
        if X[M[mid]] < X[i]:
            lo = mid+1
        else:
            hi = mid-1

    // After searching, lo is 1 greater than the
    // length of the longest prefix of X[i]
    newL = lo

    // The predecessor of X[i] is the last index of 
    // the subsequence of length newL-1
    P[i] = M[newL-1]
    M[newL] = i
    
    if newL > L:
        // If we found a subsequence longer than any we've
        // found yet, update L
        L = newL

// Reconstruct the longest increasing subsequence
S = array of length L
k = M[L]
for i in range L-1 to 0:
    S[i] = X[k]
    k = P[k]

return S
复制代码

vue3源码实现

主要思路：对数组遍历，依次求解长度为 i 时的最长递增子序列，当 i 元素大于 i – 1 的元素时，添加 i 元素并更新最长子序列；否则往前查找直到找到一个比 i 小的元素，然后插在该元素后面并更新对应的最长递增子序列。

这种做法的主要目的是让递增序列的差尽可能的小，从而可以获得更长的递增子序列，这便是一种贪心算法的思想。

function getSequence (arr) {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        // 存储在 result 更新前的最后一个索引的值
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      // 二分搜索，查找比 arrI 小的节点，更新 result 的值
      while (u < v) {
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        }
        else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]

  // 回溯数组 p，找到最终的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}
复制代码

文章版权归作者所有，未经允许请勿转载。

THE END

前端