其他
图解算法:LIS问题,单调队列+二分优化
The following article is from 小K算法 Author 小K算法
作者 | 小K
01故事起源
给你一个整数数组,如何求出其中最长的严格递增子序列的长度?
02思考
那我们要怎么确定一个元素是否应该选取到目标序列呢?咱们还是从小规模开始分析吧,懂的都懂(小K式思维法)。
03小规模分析
04抽象分析
数据规模每扩大一次,最优解也是在之前的最优解上面扩充。
05动态规划
即。
int a[100], f[100], ans = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
f[i] = 1;
for (int j = 0; j < i; ++j) {
if (a[j] < a[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
ans = max(ans, f[i]);
}
cout << ans << endl;
}
06哪里有问题呢
选取前2个长度为2,选取后2个长度也是2,但明显选取后2个更好,因为末位的高度更矮。
如果再加一个元素15,那就可以接在后面变成更大的长度3,但如果选择前面两个就不行。说明前面2个可以直接抛弃。
选取前2个长度为2,选取后3个长度为3,而且高度更矮,明显更优。说明前面2个也应该直接抛弃。
选取前2个长度为2,选取第3个长度为1。虽然前面的高度更高了,但长度也更大,不能直接抛弃。
比如再来一个元素18,就可以直接接在前面2个之后,长度为3。
如果当前数大于列尾的数,就直接加入队尾。
07算法实现
int f[1000], x, num = 0;
f[0] = 0;
for (int i = 0; i < n; ++i) {
cin >> x;
if (x == f[num]) {
continue;
}
if (x > f[num]) {
f[++num] = x;
continue;
}
int l = 0, r = num, mid;
while (l < r) {
mid = (l + r) / 2;
if (f[mid] == x) {
l = mid;
break;
}
if (f[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
//最后停留位置,>,<,=都有可能,小于更新当前位置,大于更新后一位置
if (x < f[l]) { f[l] = x; }
else if (x > f[l]) {
f[l + 1] = x;
}
}
cout << num << endl;
}
08总结
推荐阅读: