题目描述
- 最长上升子序列 II
给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
样例
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
算法1
思路:首先数组a中存输入的数(原本的数),开辟一个数组f用来存结果,最终数组f的长度就是最终的答案;假如数组f现在存了数,当到了数组a的第i个位置时,首先判断a[i] > f[cnt] ? 若是大于则直接将这个数添加到数组f中,即f[++cnt] = a[i];这个操作时显然的。
当a[i] <= f[cnt] 的时,我们就用a[i]去替代数组f中的第一个大于等于a[i]的数,因为在整个过程中我们维护的数组f 是一个递增的数组,所以我们可以用二分查找在 logn 的时间复杂的的情况下直接找到对应的位置,然后替换,即f[l] = a[i]。
我们用a[i]去替代f[i]的含义是:以a[i]为最后一个数的严格单调递增序列,这个序列中数的个数为l个。
这样当我们遍历完整个数组a后就可以得到最终的结果。
时间复杂度分析:$O(nlog n)$
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], f[maxn];
int cnt;
inline int find(int x) {
int l = 1, r = cnt;
while(l < r) {
int mid = l + r >> 1;
if(f[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int main(void) {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
f[++cnt] = a[1];
for(int i = 2; i <= n; i ++)
if(a[i] > f[cnt]) f[ ++ cnt] = a[i];
else {
int tmp = find(a[i]);
f[tmp] = a[i];
}
printf("%d\n", cnt);
return 0;
}
比y总牛逼
确实
lower_bound()写法
哦哦!懂了!当a[i] <= f[cnt] 的时,我们就用a[i]去替代数组f中的第一个大于等于a[i]的数。这里是找的第一个大于等于a[i]的数,然后把它替换成a[i]。y总找的是最大的小于a[i]的数,所以y总的代码是 q[r + 1] = a[i] ,即把找到的数的后面那个数替换成a[i],两者是等价的
然后这里为什么循环结束后直接输出f数组的长度就是答案,是因为f数组(也就是y总说的q数组)存的是每种长度的最长上升子序列的结尾的最小值。详细解释参考第一篇题解中 天蓝色鸽子的评论(点赞最多的那位大佬)
哥们,这么写虽然cnt的值是对的,但是最长子序列不对
比如10
46 -21 33 9 20 35 -41 43 -46 0 这组数据,最长上升子序列长度为5,按照题目的题意应该是-21,9,20,35,43
但是用您的这个代码逻辑输出的结果就是-46 0 20 35 43
-46,0不应该跑到20,35,43的前面
但是f数组存的本来就不是最长子序列啊
f[i]表示的是长度为i的上升子序列的结尾最小是多少
有一个疑惑就是这样的话打印出来的子序列这样它会变 , 当然子序列的长度是没有问题的 , 算是一个缺陷了
确实是这样的,1 2 4 6 3 7,输出的话是 1 2 3 6 7
可以配合一个pos数组,就能解决正确LIS输出了:
你好我想问一下,这样做子序列的长度为什么是没有问题的呀,子序列都改变了呀
可以分情况讨论一下, 如果换的是序列的中间的值的话,显然是不影响正确长度的,虽然序列不对了,如果是换的最后一个的话这个也是不影响正确长度的,并且序列是正确的,所以结果是正确的。
比楼上强
“我们用a[i]去替代f[i]的含义是:以a[i]为最后一个数的严格单调递增序列,这个序列中数的个数为l个。”
%%%%%%%%%%%
%%%%%%%%%%%
%%%%%%%%%%%
这个算法可以看懂,但怎么说明这么做就是对的呢?
尤其是else中的做法,不清楚这样做会产生什么影响QWQ
或者我这样问f的意义是什么?
leetcode上有人时这么做的叭 那上面有对应题解,去looklook
多谢仙人指点
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
不客气,一起加油
231呢?
我明白了~单调队列固然很牛逼啊
太强了xd
谢谢大佬!!!通俗易懂
妙啊
orz
呜呜呜,感谢,y总的思路着实是蚌壳住了
讲的好清楚!懂了 感谢~Orz
tql,解决了困扰我半天的问题
思路简单易懂,写的真好适合小白
比y总的代码好理解