python 查找列表中的最长子序列

cgvd09ve 于 2023-02-11 发布在 Python

关注(0)|答案(3)|浏览(115)

我想写一个函数，在线性时间内找到列表中最长的序列a_0〈= a_1〈= ...〈= a_k〉= a_（k+1）〉= ...〉= a_n。这看起来很容易，但没有嵌套的for循环，我就陷入了困境。我的想法如下：

if len(L) == 0 or len(L) == 1:
    return len(L)

if all(L[i] == L[0] for i in range(len(L)-1)):
    return len(L)

left = [1] * len(L)
right = [1] * len(L)
count = 1
for i in range(len(L)-1):
    if L[i] <= L[i+1]:
        count += 1
        left[i+1] = count
    else:
        count = 1
        left[i+1] = count

count = 1
for i in range(len(L)-1, -1, -1):
    if L[i] <= L[i-1]:
        count += 1
        right[i-1] = count
    else:
        count = 1
        right[i-1] = count

idx_left = left.index(max(left))
idx_right = right.index(max(right))

if max(max(left), max(right)) == max(left) and idx_left == len(left) - 1:
    return max(left)
elif max(max(left), max(right)) == max(right) and idx_right == 0:
    return max(right)

if idx_left == idx_right:
    return max(left) + max(right) - 1
elif idx_left < idx_right:
    return max(left) + max(right[idx_left:])
else:
    return max(left[:idx_right]) + max(right)
    
return max(max(left) + max(right[idx_left:]), max(right) + max(left[:idx_right]))

这个方法有时可以工作，但是我发现有几种情况会产生不正确的输出。你知道如何修复这个问题吗？

print(sequence([10,9,8,7,6,5,4,3,2,1])) # 10
print(sequence([1,2,3,4,5,6,7,8,9,10])) # 10
print(sequence([1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1])) # 19
print(sequence([0,0,0,0,0,0,0,0,0,0])) # 10
print(sequence([0,0,0,0,0,0,0,0,0,1])) # 10

# These cases are not working yet
print(sequence([1,0,0,0,0,0,0,0,0,1])) # 10
print(sequence([1,1,0,0,0,0,0,0,0,1])) # 10
print(sequence([1,1,1,0,0,0,0,0,0,2])) # 9

python

来源：https://stackoverflow.com/questions/75355712/find-longest-subsequence-in-a-list

3条答案

按热度按时间

jfgube3f1#

你可以试试这个：

mylist=[10,9,8,10,6,5,4,3,2,3]

previous  = mylist[0]
max_sublist = [previous]
current_sublist = [previous]
increasing = True

for x in mylist[1:]:
    if increasing and previous <= x:
        current_sublist.append(x)
    elif previous >= x:
        increasing = False
        current_sublist.append(x)
    else:
        if len(current_sublist) > len(max_sublist):
            max_sublist = current_sublist[:]
        current_sublist = [previous, x]
        increasing = True
    previous = x

if len(current_sublist) > len(max_sublist):
            max_sublist = current_sublist[:]

print(f"{max_sublist=}\n{len(max_sublist)=}")

它给出：

max_sublist=[8, 10, 6, 5, 4, 3, 2]
len(max_sublist)=7

赞(0）回复(0）举报 2023-02-11

3yhwsihp2#

试着计算两个值之间的差，我不确定它对每种情况都有效，但这是一个o（n）的开始，
我在结果中添加了1，因为它对比较进行计数，所以最后一个值不会被计数

def sequance(seq):
max_len = 0
current_len = 0
going_down = False
for i in range(len(seq)-1):
    if seq[i] == seq[i+1]:
        current_len += 1
        if max_len < current_len:
            max_len = current_len
        continue
    if seq[i] < seq[i+1]:
        if going_down:
            current_len = 1
            going_down = False
            continue
        else:
            current_len +=1
            if max_len < current_len:
                max_len = current_len
            continue

    if seq[i] > seq[i+1]:
        if going_down:
            current_len += 1
            if max_len < current_len:
                max_len = current_len
            continue
        else:
            going_down = True
            current_len += 1
            if max_len < current_len:
                max_len = current_len
return max_len + 1

[10, 9, 8, 10, 6, 5, 4, 3, 2, 3] #    7
[4, 5, 3, 2, 1, 3, 6, 4, 7] #    5
[10, 9, 8, 7, 6, 5, 4, 3, 2, 3] #    9
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] #    10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #    10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] #    19
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] #    10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] #    10
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1] #    9
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1] #    9
[1, 1, 1, 0, 0, 0, 0, 0, 0, 2] #    9

赞(0）回复(0）举报 2023-02-11

vshtjzan3#

你可以考虑分组后相同值的增加/减少状态，并跟踪之前的长度，其复杂度为O（n），只需对输入进行一次处理：

from itertools import groupby

def sequence(lst):
    max_len = 0
    prev = float('nan')
    prev_len = 0
    running_len = 0
    increasing = False
    for k, g in groupby(lst):
        L = len(list(g))
        if k < prev:
            running_len += L
            increasing = False
        else:
            if increasing:
                running_len += L
            else:
                max_len = max(max_len, running_len)
                running_len = L + prev_len
                increasing = True
        prev = k
        prev_len = L

    return max(max_len, running_len)

sequence([10,9,8,10,6,5,4,3,2,3])

输出：7

注意：itertools.groupby只是为了避免处理连续的相同值而提供的一种方便，但您不必使用它，可以自己跟踪这些值。*

其他例子：

sequence([10, 9, 8, 10, 6, 5, 4, 3, 2, 3])
#7               *   *  *  *  *  *  *

sequence([4, 5, 3, 2, 1, 3, 6, 4, 7])
#5        *  *  *  *  *

sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 3])
#9         *  *  *  *  *  *  *  *  *

sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
#10        *  *  *  *  *  *  *  *  *  *

sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
#10       *  *  *  *  *  *  *  *  *   *

sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
#19       *  *  *  *  *  *  *  *  *   *  *  *  *  *  *  *  *  *  *

sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
#10       *  *  *  *  *  *  *  *  *  *

sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 1])
#10       *  *  *  *  *  *  *  *  *  *

sequence([1, 0, 0, 0, 0, 0, 0, 0, 0, 1])
#9           *  *  *  *  *  *  *  *  *

sequence([1, 1, 0, 0, 0, 0, 0, 0, 0, 1])
#9        *  *  *  *  *  *  *  *  *

sequence([1, 1, 1, 0, 0, 0, 0, 0, 0, 2])
#9        *  *  *  *  *  *  *  *  *

重构代码

这与上面的逻辑完全相同，但是测试已经被组合，中间变量被移除，等等。

from itertools import groupby

def sequence(lst):
    max_len = prev_len = running_len = 0
    prev = float('nan')
    decreasing = False
    for k, g in groupby(lst):
        if k < prev:
            decreasing = True
        elif decreasing:
            max_len = max(max_len, running_len)
            running_len = prev_len
            decreasing = False
        prev = k
        prev_len = len(list(g))
        running_len += prev_len

    return max(max_len, running_len)

赞(0）回复(0）举报 2023-02-11

我来回答

python 查找列表中的最长子序列

3条答案

重构代码

相关问题

热门标签

最新问答