在一个数组中找到最长的子序列

Question

这里的问题是找到输入数组中所有元素都按排序顺序排列的最长子序列的长度。

例如：输入 => [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])

- ajknzhol

---

Wikipedia上有一篇关于这个问题的文章，其中包括一个高效的算法来解决它。不过，理解这个解释可能会有些困难。 - user2357112

Answer 1

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] 包含长度为 i 的子序列的最小末尾值。
• ret 的变化如下...（以给定输入 [10,22,9,11] 为例）
  • [10] - 处理第一个元素后
  • [10, 22] - 处理第二个元素后
  • [9, 22] - ... 现在长度为1的子序列的最小值是9！10被覆盖了。
  • [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]

- falsetru

---

不起作用。[9, 21, 33, 41, 60, 80] 不是 [10,22,9,33,21,50,41,60,80] 的子序列；您正在重新排序输入的元素，这是不允许的。 - user2357112

你能否请添加一些关于这个如何工作的注释？ - aIKid

@user2357112，你说得对。感谢你的评论。 - falsetru

@aIKid，我添加了一段解释。希望它可以解释这个函数的作用。 - falsetru

Answer 2

data = [100,1,2,3]

conformed = []

for i in range (0, len(data)):
   if i == 0:
      if data[1]<data[0]:
         conformed.append(data[1])
      else:
         conformed.append(data[0])
   else:
       if data[i] > data[i-1]:
          conformed.append(data[i])

print conformed, len(conformed)

- Chris vCB

---

不起作用。尝试使用 [100, 1, 2, 3]。 - user2357112

确实。已修复。虽然笨拙，但已修复。 - Chris vCB

不是固定的。尝试 [100, 200, 1, 2, 3]。 - user2357112