#MYD4. 最长上升子序列

最长上升子序列

题目描述

给定一个长度为 n 的整数序列 a_1, a_2, …, a_n。求它的最长严格上升子序列的长度(子序列不要求连续,但要求下标递增且对应元素严格递增)。

输入格式

第一行一个整数 n。第二行 n 个整数,以空格分隔。

输出格式

一行一个整数,表示最长严格上升子序列的长度。

数据范围

1 ≤ n ≤ 100000,0 ≤ a_i ≤ 10^9。

样例

6
3 1 2 1 8 6
3

说明/提示

O(n log n) 的贪心+二分或树状数组优化均可。

解析

思路(O(n log n)):维护数组 g,其中 g[k] 为长度为 k+1 的上升子序列的最小结尾。对每个 a_i 在 g 中二分第一个 ≥ a_i 的位置替换(严格上升用 lower_bound),否则延长。答案为 g 的长度。

复杂度:O(n log n)。

来源

人工命题 · 三方对比实验