AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
季之秋
,
2021-02-10 16:33:18
,
所有人可见
,
阅读 194
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int N=100010;
int a[]=new int[N];
int q[]=new int[N];//上升数组某个长度的最小值,
for(int i=0;i<n;i++) a[i]=sc.nextInt();
q[0]=Integer.MIN_VALUE; //设置边界,防止二分越界
int len=0;
for(int i=0;i<n;i++){
int l=0,r=len;//已有长度最大是len,最小是0
while(l<r){//找比a[i]小的最大值,先判断是不是比a[i]小,
int mid=l+r+1>>1;
if(q[mid]<a[i]) l=mid;
else r=mid-1;
}
q[r+1]=a[i];//存长度最小值,这样无论查那个数都可以在已知的长度上最大化长度,
len=Math.max(len,r+1);//取长度最大值
}
System.out.println(len);
}
}