查找序列的最長遞增子序列

什么是序列的最長遞增子序列？
答：在一個數值序列中，找到一個子序列，使得這個子序列元素的數值依次遞增，并且這個子序列的長度盡可能地大。這就是所謂的最長遞增子序列

from itertools import combinations
from random import sampledef subAscendingList(arr):'''返回最長遞增子序列'''for length in range(len(arr), 0, -1):#按長度遞減的順序進行查找和判斷for sub in combinations(arr, length):#判斷當前選擇的子序列是否為遞增順序；長度為arr列表的長度遞減，從arr列表中找，然后進行排列組合if list(sub) == sorted(sub):#找到第一個就返回；將得到的sub進行升序排序，若與原來的列表相等，即為遞增的列表最大長度return sub
'''
Python itertools模塊combinations(iterable, r)方法可以創建一個迭代器，
返回iterable中所有長度為r的子序列，返回的子序列中的項按輸入iterable中的順序排序。
'''arr=[]
n=int(input("請輸入給定序列的個數:"))
print("請依次輸入給定序列的值:")
for i in range(n):arr.append(int(input()))
print("最大遞增子序列為：")
print(subAscendingList(arr))

效果圖如下：