HJ103 题解 | #Redraiment的走法#

#典型的最长递增子序列问题

#动态规划五部曲-确定dp含义、写出递推公式、初始化、遍历、打印debug

#a[i]表示输入的数，dp[i]表示以a[i]为终点的最长步数

#a[j]遍历a[0]-a[i-1],如果a[j]<a[i],则dp[i]就应该等于当前的dp[i]和dp[j]+1里面的最大值，即dp[i]=max(dp[i],dp[j]+1)

#初始化这里有一点坑，要注意，应该赋值为全1，因为每一个数字最少都有一步


n=int(input())
dp=[1 for i in range(n)]
a=[int(i) for i in input().split()]
for i in range(len(a)):
    for j in range(i):
        if a[j]<a[i]:
            dp[i]=max(dp[j]+1,dp[i])
print(max(dp))