B*M
发帖数: 1340 | 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是否必要？？ | S******n
发帖数: 1009 | 2 如果你想返回那个数组的话就需要，如果只需要那个数组长度就不需要
http://en.wikipedia.org/wiki/Longest_increasing_subseq
uence
increasing subsequence
searching. It processes
longest increasing
as X[1], X[2], etc.
stored values in two
value X[k] such that there
X[k] on the range k ≤ i
【在 B*M 的大作中提到】
: 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
| B*M
发帖数: 1340 | 3 我run了程序，去掉P，一样可以返回数组，
不知道是不是我的test case太简单了，
我试了好几个，都没试出来，P什么时候才是必要的，
分析也看不出来，好像M就足够了，
【在 S******n 的大作中提到】
: 如果你想返回那个数组的话就需要，如果只需要那个数组长度就不需要
:
: http://en.wikipedia.org/wiki/Longest_increasing_subseq
: uence
: increasing subsequence
: searching. It processes
: longest increasing
: as X[1], X[2], etc.
: stored values in two
: value X[k] such that there
| j*****u
发帖数: 1133 | 4 没有仔细看wiki，如果要返回数组是需要2个array的
比如这个例子: 5 6 7 1 2
最终M = {3, 4, 2}，如果没有P，返回的数组就成了1 2 7而不是5 6 7了。
【在 B*M 的大作中提到】
: 我run了程序，去掉P，一样可以返回数组，
: 不知道是不是我的test case太简单了，
: 我试了好几个，都没试出来，P什么时候才是必要的，
: 分析也看不出来，好像M就足够了，
| a***y
发帖数: 547 | 5 try 10 20 30 40 50 1 2
what in M would be 1 2 30 40 50
【在 B*M 的大作中提到】
: 我run了程序，去掉P，一样可以返回数组，
: 不知道是不是我的test case太简单了，
: 我试了好几个，都没试出来，P什么时候才是必要的，
: 分析也看不出来，好像M就足够了，
| B*M
发帖数: 1340 | 6 您老英明，果然如此！！
多谢！！
【在 j*****u 的大作中提到】
: 没有仔细看wiki，如果要返回数组是需要2个array的
: 比如这个例子: 5 6 7 1 2
: 最终M = {3, 4, 2}，如果没有P，返回的数组就成了1 2 7而不是5 6 7了。
| B*M
发帖数: 1340 | 7 多谢！
【在 a***y 的大作中提到】
: try 10 20 30 40 50 1 2
: what in M would be 1 2 30 40 50
| P********l
发帖数: 452 | |
|
|
