有效地从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)

虽然它似乎与我尝试过的测试用例一起工作得很好，但有没有更有效的方法来做到这一点，因为对于列表已经排序的情况，这段代码的最坏转换时间复杂度是 O(n^2)，假设内置的 min 方法使用线性搜索。

更准确地说，我想要最长的非递减子列表，并且子列表应该从列表的最小元素开始。并且通过子列表，我的意思是元素不需要在给定的原始列表（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 = mineleseq = 0longest = 0longest_idx = Nonewhile ind < len(lis):&nbsp; &nbsp; if lis[ind] >= currmin:&nbsp; &nbsp; &nbsp; &nbsp; newlis[seq].append(lis[ind])&nbsp; &nbsp; &nbsp; &nbsp; currmin = lis[ind]&nbsp; &nbsp; &nbsp; &nbsp; ind += 1&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; if len(newlis[seq]) > longest:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; longest = len(newlis[seq])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; longest_idx = seq&nbsp; &nbsp; &nbsp; &nbsp; newlis.append([minele])&nbsp; &nbsp; &nbsp; &nbsp; currmin = minele&nbsp; &nbsp; &nbsp; &nbsp; seq += 1if len(newlis[seq]) > longest:&nbsp; &nbsp; longest = len(newlis[seq])&nbsp; &nbsp; longest_idx = seqprint(newlis)print(newlis[longest_idx])