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

#通过动态规划方式解决
n=int(input())
num=list(map(int,input().split()))
dp=[1]*n  #根据数组长度创建[1,1,1,1,...]的dp数组，它代表每个位置上有的最长子序列长度，它本身就是一个子序列，故而初始化为1
for i in range(n):  #遍历数组
    for j in range(i): 
        if num[i]>num[j]:  #分别比较当前数和这个数之前的数大小，如果大于就在之前的那个数位置dp数组的基础上加一并更新当前位置dp数组小大
            dp[i]=max(dp[i],dp[j]+1)  #因为我们只记录最大的，所以留下原位置和以前位置比较后的最大值来更新dp数组
print(max(dp))  #最后返回dp数组里记录的某位置最大值