我只是偶然发现了这个问题，并提出了以下Python 3实现：
def subsequence(seq): if not seq: return seq M = [None] * len(seq) # offset by 1 (j -> j-1) P = [None] * len(seq) # Since we have at least one element in our list, we can start by # knowing that the there's at least an increasing subsequence of length one: # the first element. L = 1 M[0] = 0 # Looping over the sequence starting from the second element for i in range(1, len(seq)): # Binary search: we want the largest j <= L # such that seq[M[j]] < seq[i] (default j = 0), # hence we want the lower bound at the end of the search process. lower = 0 upper = L # Since the binary search will not look at the upper bound value, # we'll have to check that manually if seq[M[upper-1]] < seq[i]: j = upper else: # actual binary search loop while upper - lower > 1: mid = (upper + lower) // 2 if seq[M[mid-1]] < seq[i]: lower = mid else: upper = mid j = lower # this will also set the default value to 0 P[i] = M[j-1] if j == L or seq[i] < seq[M[j]]: M[j] = i L = max(L, j+1) # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...] result = [] pos = M[L-1] for _ in range(L): result.append(seq[pos]) pos = P[pos] return result[::-1] # reversing
由于花了一些时间来了解算法的工作原理，所以我在评论时有些冗长，并且我还将添加一个快速解释：
seq
是输入序列。L
是一个数字：它会在循环序列时进行更新，并标记到该时刻为止发现的最长递增子序列的长度。M
是一个列表。M[j-1]
将指向的索引，seq
该索引拥有可用于（最后）构建增加的length子序列的最小值j
。P
是一个列表。P[i]
将指向的索引M[j]
在哪里。简而言之，它告诉您哪个是子序列的前一个元素。用于最后生成结果。i``seq``P
该算法如何工作：
- 处理空序列的特殊情况。
- 从1个元素的子序列开始。
- 用index循环输入序列
i
。 - 用二进制搜索发现
j
，让seq[M[j]
有<
比seq[i]
。 - 更新
P
，M
和L
。 - 追溯结果并将其返回反向。
注意：
与Wikipedia算法的唯一区别是
M列表中的偏移量1，在
X此称为
seq。我还使用Eric
Gustavson答案中显示的单元测试版本进行了稍微改进的单元测试版本，并通过了所有测试。
例：
seq = [30, 10, 20, 50, 40, 80, 60] 0 1 2 3 4 5 6 <-- indexes
最后，我们将有：
M = [1, 2, 4, 6, None, None, None]P = [None, None, 1, 2, 2, 4, 4]result = [10, 20, 40, 60]
如您所见，
P这非常简单。我们来看看它到底，所以它告诉之前
60还有的
40,前
80有
40，以前
40有
20，之前
50有
20和以前
20有
10，停止。
复杂的部分在继续
M。在开始的时候
M是
[0, None, None, ...]因为长度为1的亚序列的最后一个元素（因此位置0
M）是索引0处：
30。
此时，我们将开始循环
seq查看
10，因为
10is
<比
30，
M将被更新：
if j == L or seq[i] < seq[M[j]]: M[j] = i
所以，现在
M的样子：
[1, None, None, ...]。这是一件好事，因为
10有更多的机会来创造更长的增加的子序列。（新的1是10的索引）
现在轮到了
20。通过
10和
20我们拥有长度为2的子序列（中的索引1
M），因此
M将是：
[1, 2, None,...]。（新的2是20的索引）
现在轮到了
50。
50不会成为任何子序列的一部分，因此不会发生任何变化。
现在轮到了
40。用
10，
20和
40我们有长度为3（索引2的在子
M，所以
M将是：
[1, 2, 4, None,...]（新图4是40指数）
等等…
有关代码的完整介绍，您可以在此处复制并粘贴它：)
