403. 最长上升子序列LIS
时间限制：1000 MS 内存限制：64 MB
题目描述
# 最长上升子序列 LIS ## 题目描述 给定一个长度为 $N$ 的整数序列 $a_1,a_2,\ldots,a_N$，求其最长严格递增子序列的长度。 子序列是从原序列中选取若干项，并保持这些项在原序列中的相对顺序所得到的序列，选取的项不必连续。 严格递增是指子序列中每一项都严格小于其后一项。 ## 输入格式 输入文件为 `lis.in`。 第一行包含一个整数 $N$，表示序列的长度。 第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示给定的序列。 ## 输出格式 输出文件为 `lis.out`。 输出一个整数，表示最长严格递增子序列的长度。 ## 数据范围 - $1 \le N \le 1000$。 - $-10^9 \le a_i \le 10^9$。 时间限制：$1000$ 毫秒。 内存限制：$64$ MB。 ## 样例输入 ``` 7 3 1 2 1 8 5 6 ``` ## 样例输出 ``` 4 ``` ## 样例说明 可以选取子序列 $1,2,5,6$，其长度为 $4$，且不存在更长的严格递增子序列。