【笔记】最长递增子序列 Longest increasing subsequence(LIS)-白红宇

【笔记】最长递增子序列 Longest increasing subsequence(LIS)

阅读量：6536 次

发布时间：2019-06-24

本文共 2225 字，大约阅读时间需要 7 分钟。

介绍和解法，参见wikipedia

笔记：

在按下标顺序遍历序列 X 的过程中，记录所有不同长度 L 的增长最慢的递增子序列，因为序列是递增的，只需要记录其最大元素，记为 M[L]

比如，对于序列 5,8,9,6,7，在访问 6 之前，M[1]=5，M[2]=8，M[3]=9。

访问 6 时，长度为2 的增长最慢的递增子序列为5,6，因此 M[2] 变为 6。

同理，访问 7 时， M[3] 变为 7。

遍历结束后，M 的长度即为 LIS 的长度，但并不知道这个 LIS 是什么。

为了得到 LIS，将原来 M 保存的数据改为该数据在序列 X 中的 index；

并且，在遍历 X 的过程中，记录每个元素 X[i] 在候选的递增子序列中的前驱元素在序列 X 中的 index，记为P[i]

这样在遍历结束后，就可以从后往前输出 LIS：记 M 长度为 m，有：

LIS[m]   = X[    M[m]  ]LIS[m-1] = X[  P[M[m]] ]LIS[m-2] = X[P[P[M[m]]]]......

wikipedia 原文引用如下：

It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as X[0], X[1], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:

M[
j] — stores the index
k of the smallest value X[
k] such that there is an increasing subsequence of length
j ending at X[
k] on the range
k ≤
i. Note that
j ≤
(i+1), because
j ≥ 1 represents the length of the increasing subsequence, and
k ≥ 0 represents the index of its termination.

P[
k] — stores the index of the predecessor of X[
k] in the longest increasing subsequence ending at X[
k].

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