题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
思路
q[i]
表示长度为i,结尾最小的上升子序列的结尾。(结尾最小也意味着可拓展性最强)
可证q[i]
是单调递增的:
假设存在q[i - 1] >= q[i]
, 则在q[i]
对应的LIS中,第i - 1个元素< q[i] <= q[i - 1]
。则存在比q[i - 1]
结尾更小的,长度为i - 1的上升子序列,与前提矛盾。- 在使用二分时,注意保持区间的单调性,即区间右端点取已知最长上升子序列的长度(res)。