寻找最长递增序列 [英] Find longest increasing sequence

问题描述

您给出一个数列，你需要找到一个最长递增​​子序列从给定的输入（不需要连续）。

You are given a sequence of numbers and you need to find a longest increasing subsequence from the given input(not necessary continuous).

我发现连结此（维基百科 最长递增子），但需要更多的解释。

I found the link to this(Longest increasing subsequence on Wikipedia) but need more explanation.

如果有人可以帮助我理解为O（n log n）的实施，这将是很有益的。如果你能举个例子来说的算法中，那将是真正的AP preciated。

If anyone could help me understand the O(n log n) implementation, that will be really helpful. If you could explain the algo with an example, that will be really appreciated.

我看到其他职位还有什么，我不明白的是： L = 0  对于i = 1，2，... N：    二进制搜索的最大正Ĵ≤大号使得X [M [J〕25; X [I]（或设置J = 0，如果不存在这样的值）  上面的说法，从哪里开始的二进制搜索？如何初始化M []，X []？

I saw the other posts as well and what I did not understand is: L = 0 for i = 1, 2, ... n: binary search for the largest positive j ≤ L such that X[M[j]] < X[i] (or set j = 0 if no such value exists) above statement, from where to start binary search? how to initialize M[], X[]?

推荐答案

一个简单的问题是要找到最长增加子序列的长度。你可以专注于先理解这个问题。在算法中，唯一的区别在于，它不使用的 P 的阵列

A simpler problem is to find the length of the longest increasing subsequence. You can focus on understanding that problem first. The only difference in the algorithm is that it doesn't use the P array.

X 的是一序列的输入，因此它可以被初始化为： X = [0，8,4，12，2，10，6，14，1,9，5，13，3，11，7，15]

x is the input of a sequence, so it can be initialized as: x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

M 的跟踪的最好的子序列的每个长度的发现至今。最好是一个具有最小结束值（允许更宽范围的值后，添加）。长度和结束值被唯一需要的数据被存储为每个子序列

m keeps track of the best subsequence of each length found so far. The best is the one with the smallest ending value (allowing a wider range of values to be added after it). The length and ending value is the only data needed to be stored for each subsequence.

中的每个元素的 M 的再presents子序列中。对于 M [J] 的

Each element of m represents a subsequence. For m[j],

• 的Ĵ的是序列的长度。
• M [J] 的是索引（中的 X 的）的子序列的最后一个元素。
• 等等， X [M [J]] 的是序列的最后一个元素的值。

• j is the length of the subsequence.
• m[j] is the index (in x) of the last element of the subsequence.
• so, x[m[j]] is the value of the last element of the subsequence.

→的是迄今为止发现的最长的子序列的长度。第一次的→的值 M 的是有效的，其余都是初​​始化。的米的可与第一元件是0，其余的未初始化开始。的大号的增加​​作为算法运行时，也是如此的米的

L is the length of the longest subsequence found so far. The first L values of m are valid, the rest are uninitialized. m can start with the first element being 0, the rest uninitialized. L increases as the algorithm runs, and so does the number of initialized values of m.

下面是一个例子运行。的×〔Ⅰ〕的，并米的在每次迭代的结尾给出（但来代替索引序列的值）。

Here's an example run. x[i], and m at the end of each iteration is given (but values of the sequence are used instead of indexes).

在每个迭代的搜索是寻找在何处放置的 X [I] 的。它应该是尽可能向右尽可能（获取最长的序列），和比值到它的左更大（因此它是一个递增的序列）。

The search in each iteration is looking for where to place x[i]. It should be as far to the right as possible (to get the longest sequence), and be greater than the value to its left (so it's an increasing sequence).

 0:  m = [0, 0]        - ([0] is a subsequence of length 1.)
 8:  m = [0, 0, 8]     - (8 can be added after [0] to get a sequence of length 2.)
 4:  m = [0, 0, 4]     - (4 is better than 8. This can be added after [0] instead.)
 12: m = [0, 0, 4, 12] - (12 can be added after [...4])
 2:  m = [0, 0, 2, 12] - (2 can be added after [0] instead of 4.)
 10: m = [0, 0, 2, 10]
 6:  m = [0, 0, 2, 6]
 14: m = [0, 0, 2, 6, 14]
 1:  m = [0, 0, 1, 6, 14]
 9:  m = [0, 0, 1, 6, 9]
 5:  m = [0, 0, 1, 5, 9]
 13: m = [0, 0, 1, 5, 9, 13]
 3:  m = [0, 0, 1, 3, 9, 13]
 11: m = [0, 0, 1, 3, 9, 11]
 7:  m = [0, 0, 1, 3, 7, 11]
 15: m = [0, 0, 1, 3, 7, 11, 15]

现在我们知道有一个序列长度为6，15结尾的子序列的实际值可以通过将它们存储在被发现的 P 的循环过程中的数组。

Now we know there is a subsequence of length 6, ending in 15. The actual values in the subsequence can be found by storing them in the P array during the loop.

获取最佳的子序列：

P 的存储在最长序列（作为x的一个指数）的previous元件，对于每个数目，和被更新作为算法的进展。例如，当我们处理8，我们知道谈到0后，使存储的事实，8 0后的 P 的。您可以从像一个链表的最后一个号码向后工作得到整个序列。

P stores the previous element in the longest subsequence (as an index of x), for each number, and is updated as the algorithm advances. For example, when we process 8, we know it comes after 0, so store the fact that 8 is after 0 in P. You can work backwards from the last number like a linked-list to get the whole sequence.

因此​​，对于每一个数字，我们知道在它之前出现的次数。为了找到子结局7，我们看的 P 的，看到的是：

So for each number we know the number that came before it. To find the subsequence ending in 7, we look at P and see that:

7 is after 3
3 is after 1
1 is after 0

因此​​，我们有子序列[0，1，3，7]。

So we have the subsequence [0, 1, 3, 7].

在7或15股结尾部分号码子序列：

The subsequences ending in 7 or 15 share some numbers:

15 is after 11
11 is after 9
9 is after 6
6 is after 2
2 is after 0

因此​​，我们有子序列[0，2，6，9，11]和[0，2，6，9，11，15]（最长的递增子）

So we have the subsequences [0, 2, 6, 9, 11], and [0, 2, 6, 9, 11, 15] (the longest increasing subsequence)

这篇关于寻找最长递增序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！