最长上升子序列加强版
题目描述
给出一个由 n个不超过 10^9的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。
输入格式
第一行，一个整数 n，表示序列长度。
第二行有 n 个整数，表示这个序列。
输出格式
一个整数表示这个序列的最长上升子序列的长度。
输入输出样例
输入样例1：
7 3 1 2 5 4 9 7输出样例1：
4说明
对于20%的数据：n<=10
对于80%的数据：n<=5000
对于100%的数据：n<=1000000
对于嵌套循环超时的部分数据，可以采用二分优化：
【耗时限制】1000ms 【内存限制】512MB
参考AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL n, a, len, dp[1000010];
//可以用二分优化,下界
LL lower(LL l, LL r, LL x){
while (l < r){
LL mid = (l + r) >> 1;
if (dp[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int main(){
scanf ("%lld", &n);
for (LL i = 1;i <= n;i ++){
scanf ("%lld", &a);
if (len == 0 || dp[len] < a) dp[++ len] = a;
else dp[lower(1, len+ 1, a)] = a;
}
printf ("%lld", len);
return 0;
}
//要点：用二分进行优化，不然会超时
鼓励大家自己独立完成，不要直接抄哟~