[HDOJ3308]LCIS（线段树，区间合并，新的代码）

题目描述

给定一个长度为$n$的序列$a_1,a_2,...,a_n$，找到其中的一个最长严格上升子序列（LIS），使得其中的元素在原序列中的下标单调不降。

输入格式

第一行一个数$n$（$1\leq n\leq 10^5$），表示序列的长度。

第二行$n$个数$a_i$（$1\leq a_i\leq 10^9$），表示序列中的元素。

输出格式

输出最长上升子序列的长度。

样例输入

7
1 3 5 2 4 6 7

样例输出

4

算法1

(线段树) $O(n\log n)$

线段树维护区间最长上升子序列，用vector合并区间。

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

枚举所有的上升子序列，取其中最长的。

时间复杂度

参考文献

C++ 代码