最长上升子序列
一个元素为数值的列表，找到其最长上升子序列的长度。
比如 [5, 4, 1, 2, 5, 3]， 最长上升子序列是 [1, 2, 3], 长度为3。
例子
get_long_incr_lst(5, 4, 1, 2, 5, 3]) -> 3
get_long_incr_lst([10, 9, 2, 5, 3, 7, 101, 18]) -> 4假设
- 输入不为空
tips
- 动态规划
解法1：
def get_long_incr_lst(lst):
"""
动态规划
1. 寻找所有上升链，将列表中上升元素加入到队列
2. 遍历元素，加入到合适的上升链
:param lst:
:return:
"""
def addlist(uplist: list, i: int) -> bool:
"""
1. 遍历链条，比较两条末端元素和新元素的大小
2. 如果存在新元素大于链条末尾元素则加入链条，如果遍历完所有链条没能加入，则返回false，申请新添加一条链条
3. 当加入链条时，不会改变原来的链条，而是申请一个copy，然后加入新元素后，将新申请的链条加入到上升链集合中
:param uplist:
:param i:
:return:
"""
flag = False
for item in uplist:
if item[-1] < lst[i]:
# 获取原来的链条copy
item_copy = item.copy()
# 生成一条新的上升链
item_copy.append(lst[i])
if item_copy not in uplist:
uplist.append(item_copy)
flag = True
return flag
if not lst:
return 0
uplist = [] # 上升链集合
for i in range(len(lst)):
# 如果上升链为空，或者元素不能加入已有链条，则申请一条新链条
if not uplist or not addlist(uplist, i):
uplist.append([lst[i]])
print(uplist)
return max(map(len, uplist))