Python 求列表的最长升序子列

本文主要是介绍Python 求列表的最长升序子列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这块用到了 bisect 的二分查找模块，用于查找新元素在有序列表里边的插入位置。虽然之前有接触过 git 里边的 git bisect（用于定位某个 bug 第一次引入的 commitId），但是 python 里边对 bisect 的真正理解还是来源于下面这个例子：

import bisectinput_list = [1, 2, 4, 3, 5]sequence = []
for ele in input_list:pos = bisect.bisect_left(sequence, ele)  # 查找 ele 可以在列表 sequence 中插入的位置if pos == len(sequence):   # 如果发现插入新值的位置是在最右边，说明新元素是当前最大值，追加到列表后边sequence.append(ele)else:                      # 否则，说明 pos 位置的原有元素不比新值 ele 更大，将它替换sequence[pos] = ele
print(sequence)

[1, 2, 3, 5]

当然，列表的最长升序子列可能会不止一个，这块求出的是使得子序列 sum 最小的最长升序子列。

这篇关于Python 求列表的最长升序子列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---