#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)。
来源
人工命题 · 三方对比实验