标签 python
<分区>
这里的问题是从输入数组中找到最长子序列的长度，使得所有元素都按排序顺序排列。
示例:输入 => [10,22,9,33,21,50,41,60,80]
示例:输出 => [10,22,33,50,60,80] 是6
我的尝试:
def longest_sequence(input):
obj = []
for x in sorted(input):
obj.append(x)
print[obj, len(obj)]
# [[9, 10, 21, 22, 33, 41, 50, 60, 80], 9]
longest_sequence([10,22,9,33,21,50,41,60,80])
最佳答案
import bisect
def lis(xs):
ret = []
for x in xs:
i = bisect.bisect_left(ret, x)
ret[i:i+1] = x,
return len(ret)
例子:
>>> lis([10, 1, 2, 3])
3
>>> lis([10,22,9,33,21,50,41,60,80])
6
注意 在上面的代码中，ret 不包含有效的子序列。但是长度是对的。 使用上面的代码你想要的只是LIS的长度。
解释:
想想 [10,22,9,11]。可能有两个 LIS:[10,22]、[9,11]。上述 lis 函数中的 ret 保持以下条件:
ret 已排序；可以使用二进制搜索(bisect.bisect_left)ret[i] 包含 length-i 子序列的最小最后值。ret 更改为...(给定 [10,22,9,11] 作为输入)
时间复杂度:O(nk) 其中 n 是列表项的数量，k 是 LIS 的长度。
更新
正确获取子序列的修改版本:
import bisect
def lis(xs):
if not xs: return []
prev = {}
ret = []
for x in xs:
i = bisect.bisect_left(ret, x)
ret[i:i+1] = x,
prev[x] = ret[i-1] if i > 0 else None
subseq = [ret[-1]]
while subseq[-1] is not None:
subseq.append(prev[subseq[-1]])
return list(reversed(subseq[:-1]))
例子:
>>> lis([])
[]
>>> lis([10, 1, 2, 3])
[1, 2, 3]
>>> lis([10,22,9,33,21,50,41,60,80])
[10, 22, 33, 41, 60, 80]
>>> lis([1,5,2,6,3,4])
[1, 2, 3, 4]
>>> lis([100,200,1,2,3])
[1, 2, 3]
关于python - 查找数组中最长的子序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21060344/