# 最长递增子序列

## 例子

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

## 高效的算法

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

X[M[1]], X[M[2]], ..., X[M[L]]

A demo of the code.
```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
```

## 参考文献

1. ^ Aldous, David; Diaconis, Persi, Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem, Bulletin of the American Mathematical Society, 1999, 36 (04): 413–432, doi:10.1090/S0273-0979-99-00796-X.
2. ^ Schensted, C., Longest increasing and decreasing subsequences, Canadian Journal of Mathematics, 1961, 13: 179–191, MR 0121305, doi:10.4153/CJM-1961-015-3.
3. ^ Hunt, J.; Szymanski, T., A fast algorithm for computing longest common subsequences, Communications of the ACM, 1977, 20 (5): 350–353, doi:10.1145/359581.359603.
4. ^ Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press: 159, 1980.
5. ^ Fredman, Michael L., On computing the length of longest increasing subsequences, Discrete Mathematics, 1975, 11 (1): 29–35, doi:10.1016/0012-365X(75)90103-X.