题解 | #Redraiment的走法#

此解法应优于已经发布的动态规划解法。

n = int(input())
a = list(map(int, input().split()))

res = [max(a)+1]
for new in a:
    n = len(res)
    if new < res[0]:
        res[0] = new
    else:
        for i, y in zip(reversed(range(n)), reversed(res)):
            if new > y:
                if i == n-1:
                    res.append(new)
                else:
                    res[i+1] = min(res[i+1], new)
                break
print(len(res))