题目描述

输入一个数组，找到最长的上升子序列（子序列可以不连续）。程序只要求输出最长上升子序列的长度。

例如，数组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