题目描述
给定一个长度为 N
的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N
。
第二行包含 N
个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
样例
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
算法
(二分+贪心) $O(nlogn)$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N],a[N];
int main(){
cin >> n;
for(int i = 0;i < n;i++){
scanf("%d?",&a[i]);
}
q[0] = -2e9;
/*输入中有小于0的数,
为了保证每次更新长度为1的子序列最小值至少不会出现长度为0
这里把q[0]定的最小
*/
int len = 0;//记录最大值即答案,这里len和r都是从0开始的
for(int i = 0;i < n;i++){
int l = 0,r = len;
while(l < r){
int mid = (l+r+1)>>1;
if(q[mid] < a[i] )l = mid;
else r = mid-1;
}
len = max(len , r+1);
q[r+1] = a[i];
/* 这里直接看是查在尾部或中间,
其实的含义是找到了比a[i]小的最长子序列的结尾值
结尾值能保证最小由一直用二分查找之前的值来保证
这个q[r+1] = a[i];同时也保证了数列的递增符合了推论
*/
}
cout << len <<endl;
return 0;
}