前置
设 l o w i low_i lowi ：长度为 i i i 的上升子序列末尾数的最小值
我们要使 l o w i low_i lowi 尽量小，这样后面的元素就更有可能加入到当前的上升子序列中。
举例：
序列 A ：1 2 3
序列 B ：1 2 5
这时如果后面有一个元素是 4 4 4,它只能加入到 序列 A 序列A 序列A中,不能加入到 序列 B 序列B 序列B中。
维护
对于原序列 a a a中的每一个元素，二分找到第一个大于等于 a i a_i ai的 l o w i low_i lowi，用 a i a_i ai更新 l o w i low_i lowi。
举例：
我们用#来代表极大值( I N F INF INF)
下面我的表示方法是 数组名+下标(值)，如 a 3 ( 7 ) a_3(7) a3(7)表示数组 a a a的第3个数，它的值是7。
原序列 a a a：1 2 4 1 3 4
数组 l o w low low：# # # # # #
a
1
=
1
a_1=1
a1=1：
第一个
≥
a
1
(
1
)
\ge a_1(1)
≥a1(1)的数是
l
o
w
1
(
I
N
F
)
low_1(INF)
low1(INF)，用
a
1
(
1
)
a_1(1)
a1(1)更新
l
o
w
1
low_1
low1。
数组
l
o
w
low
low：1 # # # # #
a
2
=
2
a_2=2
a2=2：
第一个
≥
a
2
(
2
)
\ge a_2(2)
≥a2(2)的数是
l
o
w
2
(
I
N
F
)
low_2(INF)
low2(INF)，用
a
2
(
2
)
a_2(2)
a2(2)更新
l
o
w
2
low_2
low2。
数组
l
o
w
low
low：1 2 # # # #
a
3
=
4
a_3=4
a3=4：
第一个
≥
a
3
(
4
)
\ge a_3(4)
≥a3(4)的数是
l
o
w
3
(
I
N
F
)
low_3(INF)
low3(INF)，用
a
3
(
4
)
a_3(4)
a3(4)更新
l
o
w
3
low_3
low3。
数组
l
o
w
low
low：1 2 4 # # #
a
4
=
1
a_4=1
a4=1：
第一个
≥
a
4
(
1
)
\ge a_4(1)
≥a4(1)的数是
l
o
w
1
(
1
)
low_1(1)
low1(1)，用
a
4
(
1
)
a_4(1)
a4(1)更新
l
o
w
1
low_1
low1。
数组
l
o
w
low
low：1 2 4 # # #
a
5
=
3
a_5=3
a5=3：
第一个
≥
a
5
(
3
)
\ge a_5(3)
≥a5(3)的数是
l
o
w
3
(
4
)
low_3(4)
low3(4)，用
a
5
(
3
)
a_5(3)
a5(3)更新
l
o
w
3
low_3
low3。
数组
l
o
w
low
low：1 2 3 # # #
a
6
=
4
a_6=4
a6=4：
第一个
≥
a
4
(
4
)
\ge a_4(4)
≥a4(4)的数是
l
o
w
4
(
I
N
F
)
low_4(INF)
low4(INF)，用
a
6
(
4
)
a_6(4)
a6(4)更新
l
o
w
4
low_4
low4。
数组
l
o
w
low
low：1 2 3 4 # #
最长上升子序列的长度就是最大的值不为INF的下标，在此样例中就是4.
代码
以洛谷的这道题为例。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[1000005],low[1000005],len=0;
signed main(){
ios::sync_with_stdio(false);
cin>>n;
for(ll i=1;i<=n;i++)cin>>a[i];
memset(low,0x3f,sizeof(low));
for(ll i=1;i<=n;i++){
ll L=1,R=len+1,res=0;
while(L<=R){
ll mid=(L+R)>>1;
if(low[mid]>=a[i]){R=mid-1;res=mid;}
else L=mid+1;
}
low[res]=a[i];
if(res==len+1)len++;
}
cout<<len<<endl;
return 0;
}
如果你还有问题，请在评论区留言或私信，我会尽量在24小时内解答。
比起点赞和关注，我更希望你们可以说出你们不懂的地方是哪。
标签：ll,数是,二分法,ge,low,序列,INF,最长 From： https://blog.csdn.net/MC_wansui/article/details/137435683