AcWing0896 最长上升子序列 II
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N 。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1 ≤ N ≤ 100000 ,
−10\^9 ≤ 数列中的数 ≤ 10\^9
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
算法思想:
使用二分法优化的算法思想如下:
- 定义一个数组d,数组中元素表示长度为i的最长上升子序列的最后一个元素的最小值,其中i为当前考虑的子序列长度。
- 遍历原始数组nums,对于每个元素nums[i],在数组d中使用二分法找到第一个大于等于nums[i]的元素d[k],并将其替换为nums[i]。
- 如果nums[i]大于数组d中的所有元素,则将nums[i]追加到数组d的末尾。
- 最终,数组d的长度即为所求的最长上升子序列的长度。
这种算法的时间复杂度为O(nlogn),因为需要遍历原始数组一次,并在数组d中使用二分法查找插入位置。
算法1(137 ms):
int inc[0..idx]
。 inc[j] == k
表示考虑原序列的前缀子序列 arr[0..i]
中,长度为 j + 1
的上升子序列的最后一个元素的最小值为 k
。其中 j
的范围为 [0, idx]
, idx
维护 arr[0..i]
中最长上升子序列的长度,即 idx + 1
。
指针 i
遍历原序列 arr[0..n]
,共进行 n 轮迭代。对于每轮迭代:
在 inc[0..idx]
中查找第一个不小于 arr[i]
的元素,并将之替换为 arr[i]
。若未找到,则将 arr[i]
插到末尾,计数器 idx
加 1 ,即执行 inc[++idx] = arr[i]
。
当所有元素已遍历,返回 idx + 1
,即为最大上升子序列长度。
时间复杂度:O(n * log n)。其中 n 为原序列的长度。共进行 n 轮迭代,每轮使用二分法查找插入位置,时间开销为 O(log n),因此总时间为 O(n * log n)。
#include <iostream>
using namespace std;
const int N = 100000;
int arr[N], n;
// 查找第一个 不小于 val 的元素, 返回位序
int findGeq(int inc[], int low, int high, int val) {
while (low < high) {
int mid = (low + high) / 2;
if (inc[mid] >= val) {
high = mid;
}
else {
low = mid + 1;
}
}
return low;
}
int lis() {
int inc[N], idx = 0;
// i 遍历 arr[0..n-1], 共 n 轮迭代
inc[idx] = arr[0];
for (int i = 0; i < n; ++i) {
if (arr[i] > inc[idx]) {
inc[++idx] = arr[i];
}
else {
// 在 inc[0..idx] 中寻找 arr[i] 的插入位置
inc[findGeq(inc, 0, idx, arr[i])] = arr[i];
}
}
// 所有元素已遍历, 返回 idx+1
return idx + 1;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << lis();
return 0;
}
算法2(179 ms):
区别在于使用标准库函数 lower_bound(beg, end, val)
。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100000;
int arr[N], n;
int lis() {
int inc[N], idx = 0;
// i 遍历 arr[0..n-1], 共 n 轮迭代
inc[idx] = arr[0];
for (int i = 0; i < n; ++i) {
if (arr[i] > inc[idx]) {
inc[++idx] = arr[i];
}
else {
// 在 inc[0..idx] 中寻找 arr[i] 的插入位置
*lower_bound(inc, inc + idx + 1, arr[i]) = arr[i];
}
}
// 所有元素已遍历, 返回 idx+1
return idx + 1;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << lis();
return 0;
}