Exercises 15.4-5

Give an \(O(n^2)\)-time algorithm to find the longest
monotonically increasing subsequence of a sequence of n
numbers。

  • 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的博客,茅塞顿开。

算法导论接下来的一题要求用O(nlg n)-求出最长子序列.。

Exercises 15.4-6: ⋆

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 ki (note we have jki 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