题目大意
求一个数组里最长不升子序列的个数
题目解法
考虑到已经有 O(n^2) 题解了
这里提供 O(n log n) 解法
我们可以用二分来解决问题
需要用到Dilworth 定理，即将一个序列分成若干个最长不升子序列的个数=这个序列里最长上升子序列的长度
求数组的 LIS （即最长上升子序列）
我们可以用一个 f 数组来记录当前长度为 x 的上升子序列中尾元素的最小值
f 数组一定是单调递增的，因为子序列是上升的，且长度为 x+1 的序列是通过在长度为 x 的序列后面添加一个元素形成
计算当前最长上升子序列的长度 ans 时只需在 f 数组中找到最后一个小于 a[i] 的元素（二分求下标）
核心代码
for (int i = 1; i <= n; i++) {//枚举当前长度为 i 的上升子序列
l = 1;
r = i;
while (l < r) {
mid = (l + r) / 2;
if (f[mid] >= a[i]) {
r = mid;
} else {
l = mid + 1;
}
}//二分求下标
f[l] = min(f[l], a[i]);//对a[i]加到长度为l的上升子序列中，处理尾元素
ans = max(ans, l);
}
不要忘记 f 数组初始化成最大值！！！
共 1 条回复
666居然盗我头像