每日一题————2026-6-28 最长上升子序列加强版（线性DP版）

最长上升子序列加强版

题目描述

给出一个由 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;
}

//要点：用二分进行优化，不然会超时

鼓励大家自己独立完成，不要直接抄哟~