最长上升子序列加强版题目描述给出一个由 n个不超过 10^9的正整数组成的序列。请输出这个序列的最长上升子序列的长度。最长上升子序列是指从原序列中按顺序取出一些数字排在一起这些数字是逐渐增大的。输入格式第一行一个整数 n表示序列长度。第二行有 n 个整数表示这个序列。输出格式一个整数表示这个序列的最长上升子序列的长度。输入输出样例输入样例17 3 1 2 5 4 9 7输出样例14说明对于20%的数据n10对于80%的数据n5000对于100%的数据n1000000对于嵌套循环超时的部分数据可以采用二分优化【耗时限制】1000ms 【内存限制】512MB参考AC代码#include bits/stdc.husing 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;}//要点用二分进行优化不然会超时鼓励大家自己独立完成不要直接抄哟~