LISnlogn写法
下面给出两种简单的dp写法:
代码1:
1 | long long a[100010]; |
代码2:
1 | long long a[100010]; |
不过dp的时间复杂度显然是$O(n^2)$,我们可以用贪心的思想优化到$O(nlogn)$。
原理基础:
1.我们定义一个f[]数组,其中f[i]记录长度为len的最长上升子序列的最后一个数。
2.显然,当一个最长上升子序列长度确定时,我们总是希望最后一个元素尽可能小,这样我们更有可能在后面继续插入元素。
3.由于是求最长上升子序列,设y=f[i],其中随着i的增大,y肯定会增大,因此f数组是一个满足单调性的数组,所以我们可以用二分,这也是$O(nlogn)$时间复杂度的保障。
具体代码实现看代码以及注释:
1 |
|