O(nlogn)
STL:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N];
vector<int> q;
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
for(int i = 0; i < n; i ++)
{
int t = lower_bound(q.begin(), q.end(), a[i]) - q.begin();
if(t == q.size()) q.push_back(a[i]);
else q[t] = a[i];
}
//q[0] 长度为1的子序列最末尾数的最小值
printf("%d\n", q.size());
return 0;
}
/*
下面是模拟STL的做法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int q[N]; //q[i] 当前长度为i + 1的子序列结尾数的最小值
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
int len = 0; //q中最后一个元素的下标
q[0] = a[0]; //初始化
for(int i = 1; i < n; i ++)
{
if(q[0] >= a[i]){ //如果不特判的话边界很麻烦
q[0] = a[i];
continue;
}
int l = 0, r = len;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] >= a[i]) r = mid - 1;
else l = mid;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
printf("%d\n", len + 1);
return 0;
}
*/
手写二分:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int q[N]; //q[i] 当前长度为i的子序列结尾数的最小值, 由子序列严格单调递增+反证可得严格单调递增
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
/*
从1开始二分的做法
int len = 1;
q[1] = a[0];
for(int i = 1; i < n; i ++)
{
int l = 1, r = len; //如果想要从1开始找,找不到比a[i]小的数, 那么默认找到q[1], 则需要特判
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] >= a[i]) r = mid - 1; //找小于a[i]最大的那个数
else l = mid;
}
if(a[i] > q[r]) //如果找到了小于a[i]最大的那个数
{
len = max(len, r + 1);//更新最大长度
q[r + 1] = a[i];//因为二分, q[r]小于a[i], q[r + 1] >= a[i], 所以直接更新
}else //如果没找到, 那么更新最小的那个数
{
q[1] = a[i];
len = max(1, len);//如果len初始为0,i初始为0,没有初始化q[1]
}
}
下面是从0开始二分的做法,代码上更加简洁
*/
int len = 0;
/*
q[0] = -2e9;//哨兵
为什么不需要哨兵呢?
如果找不到比a[i]小的数, 那么默认找到q[0],把q[1]更新为a[i],仍然正确
即在二分的过程中, 由于我们mid = l + r + 1 >> 1,所以二分到q[0]和q[1]时,
不管q[0]是多少,如果q[1]>=a[i],结果就是q[0]
*/
for(int i = 0; i < n; i ++)
{
int l = 0, r = len;
//为什么要从0开始计数? 因为二分可能找不到比a[i]小的数, 那么l=r=0,len=1,q[1]=a[i],不需要特判了
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] >= a[i]) r = mid - 1; //找小于a[i]最大的那个数
else l = mid;
}
len = max(len, r + 1);//更新最大长度
q[r + 1] = a[i];//因为二分, q[r]小于a[i], q[r + 1] >= a[i], 所以直接更新,**这一步是关键**
}
printf("%d\n", len);
return 0;
}