Give an \(O(n^2)\)-time algorithm to find the longest
monotonically increasing subsequence of a sequence of n
- Let X is the sequence of the sequence of n numbers.
- Let Y is the sorted number of the sequence of that n numbers.
- Find the LCS of the X and Y.
一开始没想出来，网上搜到Rip’s Infernal Majesty的博客，茅塞顿开。
Give an O(n lg n)-time algorithm to find the longest
monotonically increasing sub-sequence of a sequence of n numbers.
(Hint: Observe that the last element of a candidate subsequence of
length i is at least as large as the last element of a candidate
subsequence of length i - 1. Maintain candidate subsequences by
linking them through the input sequence.)
Rip’s Infernal Majesty的答案，留待来日慢慢回味。
We can solve the longest increasing subsequence problem using only
arrays and binary search. It processes the sequence elements in order,
for each new X[i], maintaining a candidate sequence S by:
• if X[i] is larger than the last element in S, add X[i] into S.
• otherwise, find the smallest element that is larger than X[i], S[k]
< X[k] and X[i] ≤ S[k+1], replace S[k+1] with X[i].
After finishing processing all n numbers, the length of S is is length
of LIS of X.
LIS(X, n) 1 L = 0 2 for *i* = 1, 2, … n 3 binary search for the largest positive *j* ≤ L such that X[M[*j*]] < X[*i*] (or set *j* = 0 if no such value exists) 4 P[*i*] = M[*j*] 5 if *j* == L or X[*i*] < X[M[j+1]] 6 M[*j*+1] = *i* 7 L = max(L, *j*+1)
The algorithm stores values in two arrays:
• M[j] — stores the position 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 we have j ≤ k ≤ i here).
• P[k] — stores the position of the predecessor of X[k] in the
longest increasing subsequence ending at X[k].
L is the length of the longest increasing sequence. The actual longest
sequence can be found by backtracking through the P array: the last
item of the longest sequence is in X[M[L]], the second-to-last item is
in X[P[M[L]]], etc. Thus, the sequence has the form
…, X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].
Because the algorithm performs a single binary search per sequence
element, its total time can be expressed using as O(n log n).
问题来自算法导论，参考博客：Rip’s Infernal Majesty