# 最长单调子序列问题

##### Exercises 15.4-5

Give an \(O(n^2)\)-time algorithm to find the longest

monotonically increasing subsequence of a sequence ofn

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*(*n*lg *n*)-求出最长子序列.。

#### Exercises 15.4-6: ⋆

Give an

O(nlgn)-time algorithm to find the longest

monotonically increasing sub-sequence of a sequence ofnnumbers.

(Hint:Observe that the last element of a candidate subsequence of

lengthiis at least as large as the last element of a candidate

subsequence of lengthi- 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 positionkof the smallest value X[k] such

that there is an increasing subsequence of lengthjending at X[k]

on the rangek≤i(note we havej≤k≤ihere).

• 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(nlogn).

问题来自算法导论，参考博客：Rip’s Infernal Majesty