AcWing 896题：如何用贪心算法求解最长上升子序列II问题？

本文共计402个文字，预计阅读时间需要2分钟。

题目链接+题目描述+给定一个长度为N+的数列，求数值严格单调递增的子序列的长度最长是多少。+1≤N≤1000000+题目模型+题目分析：+对于下图所表示的样例，当某一点能放3后，背面时，可能存在+

题目链接

---

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
1≤N≤100000

题目模型

• 题目分析：

1. 对于下图所示样例，当某一个数能放在3后面时，肯定能放在1后面。所以我们只需记录每一个长度下最后一个元素的最小值是多少就可以了。
   
2. 用q[i]数组记录长度为i的上升子序列最后一个值是多少。
3. 对于每一个a[i]结尾的上升子序列，我们只需二分找到每种长度下小于a[i]的最大值，假设对应长度为4，此时q5≥a[i]，所以需要更新q5的值。