最长上升子序列(LIS)
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
输入一个数组，找到最长的上升子序列（子序列可以不连续）。程序只要求输出最长上升子序列的长度。
例如，数组a = {1, 2, 3, -1, -2, 7, 9}，它的最长上升子序列是{1, 2, 3, 7, 9}，长度为5。另外，还有一些子序列是上升子序列，比如{1, 2, 3}，{-2, 7, 9}等，但都不是最长的。
输入格式
第一行一个正整数n(1≤n≤100)，代表数组长度；
第二行n个正整数ai(-100≤ai≤100)，代表数组的每个元素。
输出格式
一个整数表示答案。
输入/输出样例
5
9 3 6 2 7
3
样例解释
最长上升子序列是{3, 6, 7}，长度3。
说明/提示
时间1000ms，内存256MiB