题目描述

blablabla

样例

blablabla

算法

(DP) $O(n^2)

blablabla

C++ 代码

if __name__ == '__main__':
    n = int(input())
    nums = list(map(int, input().split()))

    dp = [1 for _ in range(n)]

    # 记录序列当前元素的前一个元素的索引
    pre = [-1 for _ in range(n)]
    last = 0
    res = 1
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if dp[j] + 1 > dp[i]:
                    last = i
                    pre[i] = j
                    dp[i] = dp[j] + 1
            res = max(res, dp[i])


    seq = []
    while last >= 0:
        seq.append(nums[last])
        last = pre[last]

    seq.reverse()

    print(res)