从python列表高效地获取非递减子序列

Question

我编写了一个代码从python列表中获取非递减子序列

lis = [3, 6, 3, 8, 6, 4, 2, 9, 5]
ind = 0
newlis = []
while ind < len(lis):
    minele = min(lis[ind:])
    newlis.append(minele)
    ind = lis.index(minele) + 1
print(newlis)

虽然我尝试过的测试用例似乎可以很好地工作，但是有没有更有效的方法来做到这一点，因为对于列表已经排序的情况，假设内置的min方法使用线性搜索，这段代码最糟糕的转换时间复杂度是O（n^2）。你知道吗

更准确地说，我想要尽可能长的非递减子列表，子列表应该从列表的最小元素开始。对于子列表，我的意思是元素不必在给定的原始列表（lis）中处于连续的延伸中。你知道吗

Answer 1

我几乎确信它可以在线性时间内运行。你只需要在一次扫描中不断尝试构建一个最长的序列，要么像我一样存储所有序列，要么保持当前最长的序列。你知道吗

lis = [9, 1, 3, 8, 9, 6, 9, 8, 2, 3, 4, 5]
newlis = [[]]
minele = min(lis)
ind = lis.index(minele)
currmin = minele
seq = 0
longest = 0
longest_idx = None
while ind < len(lis):
    if lis[ind] >= currmin:
        newlis[seq].append(lis[ind])
        currmin = lis[ind]
        ind += 1
    else:
        if len(newlis[seq]) > longest:
            longest = len(newlis[seq])
            longest_idx = seq
        newlis.append([minele])
        currmin = minele
        seq += 1

if len(newlis[seq]) > longest:
    longest = len(newlis[seq])
    longest_idx = seq

print(newlis)
print(newlis[longest_idx])