题解 | #Redraiment的走法#

'''
解题思路：
动态规划，最长上升子序列
dp[i]定义：在位置i处结束的，最长上升子序列长度
更新公式：当L[i]>L[j]时，p[i]= max(dp[j]+1, dp[i])，j为i之前所有的位置
边界条件：dp[i] = 1
'''
while 1:
    try:
        pass

        n = int(input())
        L = list(map(int,input().strip().split()))
        #print('n=',n)
        #print('L=',L)

        #------------------------------
        # dp[i],0<=i<=n-1,以i为终点上升子序列的最大长度

        dp = [1]*n 
        maxLen = 0

        for i in range(1,n):                    # 第i个桩高度L[i]
            for j in range(0,i):                # 第0~i-1个桩调度L[0]~L[i-1]
                if L[i]>L[j]:                   # 如果存在L[i]>L[j]则maxLen[i]需更新
                    dp[i]= max(dp[j]+1, dp[i])  # 在0<=j<=i-1中，保留更大的更新
            if dp[i]>maxLen:
                maxLen = dp[i]                  # 最大的更新对maxLen[i]赋值
        print(maxLen)                           # 对所有maxLen[i]取最大

    except:
        break