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

介绍和解法，参见wikipedia https://en.wikipedia.org/wiki/Longest_increasing_subsequence

笔记：

在按下标顺序遍历序列 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

 

 

相关问题：

最长先递增再递减子序列  牛客网 https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4?tpId=37&tqId=21247&tPage=1&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

看了解法，思路如下：

遍历序列 X，得到以 X[i] 结尾的 LIS 的长度 Li[i] 和以 X[i] 开始的 LDS 的长度 Ld[i]， 找到 Li[i] + Ld[i] 的最大值；

将 X 反向再求 LIS  即最长递减子序列 LDS；

在上述解法中加入 Li[i]：Li[i] = L[P[i]] + (newL > L) ? 1 : 0

 

最长公共子序列 Longest Common Subsequence(LCS)  可参见算法导论

TODO: Longest Common Subsequence for Multiple Sequences https://stackoverflow.com/questions/5752208/longest-common-subsequence-for-multiple-sequences