题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
样例
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
算法
(贪心+二分) $O(nlog(n)$
思想:
1. 维护一个q[r]数组,q[1],q[2],…,q[r] 表示长度为1,2,…,r的子序列的最小结尾值(因为长度为1或者r的子序列可能有多个)。
2. 因为子序列长度要增加,所以在q[r]中有性质:q[1]< q[2] < … < q[r];
3. 寻找最长上升子序列,遍历a[i],就是看a[i]是否有资格存在q[r]数组中。
资格: 通过二分查找q[r]数组中,a[i]能所处的位置,进行更新or扩展q[r]数组
4.如何理解更新:就是以a[i]结尾长度为r+1的子序列,此时a[i]是最小结尾。
5.如何理解扩展:就是在q[r]数组中没有比a[i]大的最小数,那么此时我们的子序列长度len++,q[len] =a[i];
时间复杂度
$O(nlog(n)$
参考文献
https://www.acwing.com/solution/content/23960/
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int q[N];//q[r]表示长度为r的序列长度结尾的最小值
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
q[0] = -2e9;
int len = 0;//前i个数中最大的最长上升子序列的值
for (int i = 1; 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;
else r = mid - 1;
}
len = max(len, r + 1);//if len = r + 1, 意味着a[i] 比q[len]大
q[r + 1] = a[i];//这部是要把a[i]放在所找到位置后面
}
cout << len << endl;
return 0;
}