结论:最长上升子序列中的某一位a[i]
,必定是长度为i
的子序列的最后一位中最小的一个。
证明来自 https://blog.csdn.net/weixin_72060925/article/details/128429202
设q[i]为长度为i的子序列中,最小的最后一个
算法:找到一个k使得q[k]<a[i]<q[k+1]
同时更新q[k + 1] = a[i]
由于k满足单调性,所以可以二分
时间复杂度O(nlogn)