最长上升子序列

题目描述

给定一组正整数a_1,a_2,...,a_n,求其最长上升子序列。就是选择其中的若干元素，并保持其左右顺序不变。使得最终选出的序列元素单调递增，并使得长度尽可能的长。

例4， 9， 7， 1，2, 6, 3, 5， 8的最长上升子序列为1,2,3,5,8

输入

第一行为一个正整数n。 第二行为n个正整数a_1, a_2, ..., a_n.

输出

最长上升子序列的长度

样例

提示

n < 1000

来源

动规专题