题解 | #最长上升子序列(一)#

import sys
from collections import deque

n = list(map(int, input().split()))[0]
arr = list(map(int, input().split()))
dp = [[] for _ in range(n)]
dp[0].append(1)

for i in range(1,n):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i].append(max(dp[j])+1)
        else :
            dp[i].append(1)
        
print(max(list(map(max,dp))))

思路都一致：

让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前 i 个数以A[ i ]结尾的最长上升子序列长度。

　　前1个数 d(1)=1 子序列为2；

　　前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

　　前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

　　前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

　　前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

　　前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

　　前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

　　前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8

　　前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9

　　d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

主要是最后的结果，用到了map函数求二维列表每行的最大值。