给定一个数字序列，您需要从给定的输入中找到最长的递增子序列(不一定是连续的)。
我找到了指向此 ( Longest increasing subsequence on Wikipedia ) 的链接，但需要更多解释。
如果有人能帮助我理解 O(n log n) 实现，那将非常有帮助。如果您能举例说明该算法，我们将不胜感激。
我也看了其他帖子，我不明白的是: 大号 = 0 对于 i = 1, 2, ... n: 二进制搜索最大正 j ≤ L 使得 X[M[j]] < X[i](或者如果不存在这样的值则设置 j = 0) 上面的语句，从哪里开始二分查找？如何初始化M[]、X[]？
最佳答案
一个更简单的问题是找到最长递增子序列的长度。您可以先专注于理解该问题。该算法的唯一区别是它不使用 P 数组。
x 是一个序列的输入，所以可以初始化为: x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
m 跟踪迄今为止找到的每个长度 的最佳子序列。最好的是具有最小结束值的那个(允许在它之后添加更大范围的值)。长度和结束值是每个子序列唯一需要存储的数据。
m 的每个元素代表一个子序列。对于m[j]，
- j 是子序列的长度。
- m[j] 是子序列最后一个元素的索引(在 x 中)。
- 因此，x[m[j]] 是子序列最后一个元素的值。
L 是迄今为止找到的最长子序列的长度。 m 的前 L 个值是有效的，其余未初始化。 m 可以从第一个元素为 0 开始，其余元素未初始化。 L随着算法的运行而增加，m的初始化值个数也随之增加。
这是一个示例运行。 x[i]，并在每次迭代结束时给出 m(但使用序列的值而不是索引)。
每次迭代中的搜索都是寻找放置 x[i] 的位置。它应该尽可能向右(以获得最长的序列)，并且大于其左侧的值(因此它是一个递增的序列)。
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 数组中找到。
检索最佳子序列:
P 为每个数字存储最长子序列中的前一个元素(作为 x 的索引)，并随着算法的推进而更新。例如，当我们处理 8 时，我们知道它在 0 之后，所以将 8 在 0 之后的事实存储在 P 中。您可以像链表一样从最后一个数字向后工作以获得整个序列。
因此对于每个数字，我们都知道它之前的数字。要找到以 7 结尾的子序列，我们查看 P 并看到:
7 is after 3
3 is after 1
1 is after 0
所以我们有子序列 [0, 1, 3, 7]。
以 7 或 15 结尾的子序列共享一些数字:
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](最长递增子序列)
关于algorithm - 找到最长的递增序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4938833/