-3

我有一个值序列 [1,2,3,4,1,5,1,6,7]，我必须找到长度增加的最长子序列。但是，一旦达到比前一个低的数字，该函数就需要停止计数。在这种情况下，此序列中的答案是 [1,2,3,4]。因为它在重置之前有 4 个值。我将如何为此编写 Python 代码？

注意：找到“最长增加子序列”似乎是一个常见的挑战，所以在网上搜索我发现很多解决方案可以计算整个序列的长度，并返回一个增加值的子序列，忽略任何减少，所以在在这种情况下，它将返回 [1,2,3,4,5,6,7]。那不是我要找的。

它需要对每个子序列进行计数，并在达到低于前一个的数字时重置计数。然后它需要比较所有计数的子序列，并返回最长的一个。

提前致谢。

4

3 回答 3

1

考虑一个生成所有可能的升序子序列的函数，您将从一个空列表开始，添加项目，直到一个元素小于（或等于？）前一个元素，此时您保存（yield）子序列并以新的子序列重新开始。

使用生成器的一种实现可能是：

def all_ascending_subsequences(sequence):
    #use an iterator so we can pull out the first element without slicing
    seq = iter(sequence)

    try: #NOTE 1
        last = next(seq)  # grab the first element from the sequence
    except StopIteration: # or if there are none just return
        #yield [] #NOTE 2
        return

    sub = [last]
    for value in seq:
        if value > last: #or check if their difference is exactly 1 etc.
            sub.append(value)
        else: #end of the subsequence, yield it and reset sub
            yield sub
            sub = [value]
        last = value

    #after the loop we send the final subsequence
    yield sub

关于处理空序列的两个注意事项：

  1. 要完成一个生成器 aStopIteration需要被提升，这样我们就可以让它从next(seq)传播出去 - 但是当from __future__ import generator_stop它生效时，它会导致 a RuntimeErrorso 与未来兼容，我们需要明确地捕获它return。
  2. 正如我写的那样，将一个空列表传递给 all_ascending_subsequences不会生成任何值，这可能不是所需的行为。传递空列表时，请随意取消注释yield []以生成空列表。

然后你可以通过调用max结果来获得最长的时间key=len

b =  [1,2,3,4,1,5,1,6,7]

result = max(all_ascending_subsequences(b),key=len)
print("longest is", result)

#print(*all_ascending_subsequences(b))
于 2016-11-18T23:08:57.367 回答
0

您需要执行以下操作：

  1. 创建一个W给定列表的函数，返回从列表开始没有严格增加的最后一项的索引。

    • 例如，给定以下列表：[1,2,3,4,1,2,3], [4,2,1], [5,6,7,8]，它应该分别为每个列表返回4, 1,4

  2. 创建一个变量maxim并将值设置为0

  3. 重复执行以下操作，直到您的列表为空
    • 调用W列表中的函数，然后调用返回值x
    • 如果x大于maxim
      • 设置maxim为x
      • 此时，如果您希望存储此序列，您可以使用list-slice 表示法来获取包含该序列的列表部分。
    • 从列表中删除列表的那部分

最后，打印maxim，如果您要存储列表中包含最长序列的部分，则打印您得到的最后一个

于 2016-11-18T01:58:44.880 回答
0 
b = [4,1,6,3,4,5,6,7,3,9,1,0]

def findsub(a):
  start = -1
  count = 0
  cur = a[0]
  for i, n in enumerate(a):
    if n is cur+1:
      if start is -1:
        start = i - 2
        count=1
      count+=1
      cur = n
    if n < cur and count > 1:
      return [a[j] for j in range(start,start+count+1)]


print findsub(b)

一个有点草率的算法，但我相信它可以满足您的需求。通常我不会简单地向您展示代码，但我怀疑这就是您想要的，我希望您可以从中学习，并根据您所学的内容创建自己的代码。

一种更好看的方式，因为我不喜欢这样：

b = [1,2,0,1,2,3,4,5]

def findsub(a):
  answer = [a[0]]
  for i in a[1:]:
    if answer[-1] + 1 is i:
      answer.append(i)
    if not len(answer) > 1:
      answer = [i]
    elif i < answer[-1] and len(answer) > 1:
      return answer
  return answer



print findsub(b)
于 2016-11-18T01:16:36.520 回答