您将获得一系列数字,您需要从给定输入中找到最长的增加子序列(不必连续).
我找到了这个链接(维基百科上增长最快的子序列)但需要更多解释.
如果有人能帮助我理解O(n log n)实现,那将非常有用.如果你能用一个例子解释算法,那将非常感激.
我也看到了其他帖子,我不明白的是:L = 0表示i = 1,2,...... n:二元搜索最大正j≤L,使得X [M [j]] <X [i](或设置j = 0,如果没有这样的值存在)上面的语句,从哪里开始二进制搜索？如何初始化M [],X []？
fgb*_*fgb 98
一个更简单的问题是找到最长的增长子序列的长度.您可以首先专注于理解该问题.算法的唯一区别是它不使用P数组.
x是序列的输入,因此它可以初始化为:x = [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
m跟踪到目前为止发现的每个长度的最佳子序列.最好的是具有最小结束值的那个(允许在其后添加更宽范围的值).长度和结束值是每个子序列需要存储的唯一数据.
m的每个元素代表一个子序列.对于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在P之后为0的事实.您可以从最后一个数字向后工作,如链接列表,以获得整个序列.
因此,对于每个数字,我们知道它之前的数字.为了找到以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](最长的子序列)