题目描述
给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
思路
采用的思想是
利用单调队列来记录不同长度中子序列中最小的值
比如数组
3 1 2 1 8 5 6
对于i = 3, 1
长度1 它的前面3, 1中选择小的 1
长度2 它的前面2
我们推一推代码中的思路
初始化 0 位置为哨兵 -2e9
二分查找 q = [-2e9]
1. 3 >= -2e r = 0 q = [-2e9, 3] len = 1
2. 1 >= -2e r = 0 q = [-2e9, 1] len = 1
3. 2 >= 1 r = 1 q = [-2e9, 1, 2] len = 2
4. 1 >= -2e9 r = 0 q = [-2e9, 1, 2] len = 2
5. 8 >= 2 r = 2 q = [-2e9, 1, 2, 8] len = 3
6. 5 >= 2 r = 2 q = [-2e9, 1, 2, 5] len = 3
7. 6 >= 5 r = 3 q = [-2e9, 1, 2, 5, 6] len = 4
很容易发现,队列结束后保持了单调性
可行的理由:
假设队列是保持单调性,假设q[5] < q[6]。
反证法:
假设如果q[5] >= q[6], 即在长度为6的子序列中最小的值比长度为5的子序列中最小的值还要小,
明显矛盾,一旦6出现了比5还小的,定义上利用单调队列来记录不同长度中子序列中最小的值,
即5中子序列最小的比当前6中子序列最小值还小才满足单调队列
所以找第一个大于等于当前a[i]值的q[j], 让q[j] = a[i]
c++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N];
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
int len = 0; //最长上升子序列的长度
q[0] = -2e9; //哨兵
for(int i = 0; i < n; i ++){
int l = 0, r = len;
while(l < r){ //找q >= a[i]
int mid = l + r + 1 >> 1;
if(q[mid] < a[i]) l = mid; //找到大于等于a[i]的位置
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
printf("%d\n", len);
// for(int i = 1; i <= len; i ++) printf("%d ", q[i]);
return 0;
}