longest increasing subsequence O(NlogN)算法中数组 P 是否必# JobHunting - 待字闺中
B*M
1 楼
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
Efficient algorithms
The algorithm outlined below solves the longest increasing subsequence
problem efficiently, using only arrays and binary searching. It processes
the sequence elements in order, maintaining the longest increasing
subsequence found so far. Denote the sequence values as X[1], X[2], etc.
Then, after processing X[i], the algorithm will have stored 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].
In addition the algorithm stores a variable L representing the length of the
longest increasing subsequence found so far.
Note that, at any point in the algorithm, the sequence
X[M[1]], X[M[2]], ..., X[M[L]]
is nondecreasing. For, if there is an increasing subsequence of length i
ending at X[M[i]], then there is also a subsequence of length i-1 ending at
a smaller value: namely the one ending at X[P[M[i]]]. Thus, we may do binary
searches in this sequence in logarithmic time.
这里的数组P是否必要？？
Efficient algorithms
The algorithm outlined below solves the longest increasing subsequence
problem efficiently, using only arrays and binary searching. It processes
the sequence elements in order, maintaining the longest increasing
subsequence found so far. Denote the sequence values as X[1], X[2], etc.
Then, after processing X[i], the algorithm will have stored 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].
In addition the algorithm stores a variable L representing the length of the
longest increasing subsequence found so far.
Note that, at any point in the algorithm, the sequence
X[M[1]], X[M[2]], ..., X[M[L]]
is nondecreasing. For, if there is an increasing subsequence of length i
ending at X[M[i]], then there is also a subsequence of length i-1 ending at
a smaller value: namely the one ending at X[P[M[i]]]. Thus, we may do binary
searches in this sequence in logarithmic time.
这里的数组P是否必要？？
