题目背景

2023.8.21 DP 训练赛 T1

题目描述

小 A 是一位认真勤奋的教练，小 D 也是，他们都喜欢把课上讲过的题目拿来考试。

给定一个长度为 $n$ 序列 $A$，求该序列的最长上升子序列。

对于一个序列 $S$ ，我们认为其的一个上升子序列 $T$ 为 $S$ 中的一个子序列且对于所有的元素满足 $T_i<T_{i+1}$。

格式

输入格式

输入共两行。

第一行，输入一个数 $n$，表示该序列的长度。

第二行，输入 $n$ 个数，表示序列 $A$。

输出格式

输出一个数 $ans$，表示最长上升子序列的长度。

样例

5
1 3 2 4 4

3

10
1 65 2 59 28 10 94 11 30 10

5

样例解释

样例解释 1

最长子序列为 $[1,2,4]$ 或者 $[1,3,4]$，长度均为 $3$，可以证明没有更优解。

样例解释 2

最长子序列为 $[1,2,10,11,30]$，长度为 $5$，可以证明没有更优解。

数据范围

对于 $100\%$ 的数据，保证 $n\leq 2000,A_i\leq 10^5$。

时空限制：1000ms/256MB。