最长上升子序列

题目描述

给定一个长度为 $N$ 的整数序列 $a_1, a_2, \ldots, a_N$，请你找出其中最长的严格上升子序列的长度。

子序列的定义是：从原序列中删除若干个元素（也可以不删除）后得到的新序列，保持剩余元素的相对顺序不变。

严格上升的定义是：对于序列中的任意相邻两个元素 $b_i$ 和 $b_{i+1}$，都满足 $b_i < b_{i+1}$。

例如：序列 $[10, 9, 2, 5, 3, 7, 101, 18]$ 的最长上升子序列是 $[2, 3, 7, 18]$ 或 $[2, 5, 7, 101]$，长度为 $4$。

输入格式

输入共两行：

• 第一行：一个正整数 $N$（$1 \leq N \leq 5000$），表示序列长度；
• 第二行：$N$ 个整数（$-10^9 \leq$ 整数 $\leq 10^9$），表示序列中的各个元素，数字间用空格隔开。

输出格式

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

输入输出样例 #1

输入 #1

8
10 9 2 5 3 7 101 18

输出 #1

4

输入输出样例 #2

输入 #2

6
1 3 6 7 9 41

输出 #2

6

提示

数据规模与约定

• 对于 $30\%$ 的数据，$N \leq 20$；
• 对于 $60\%$ 的数据，$N \leq 500$；
• 对于 $100\%$ 的数据，$1 \leq N \leq 5000$，序列中元素的绝对值不超过 $10^9$。