AcWing 896. 最长上升子序列 II —— Java版代码
原题链接
中等
作者:
yqh
,
2020-12-23 10:36:42
,
所有人可见
,
阅读 448
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] temp = reader.readLine().split(" ");
int n = Integer.parseInt(temp[0]);
//数组a用来存储读入的数据,q用来存储长度为数组下标的最长上升子序列的最后一个元素的最小值
int[] a = new int[n+1], q = new int[n+1];
temp = reader.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(temp[i]);
}
int length = 0;q[0] = (int) -2e9;//这里将0号位初始化为一个极小值,方便计算边界
for (int i = 0; i < n; i++) {
int l = 0, r = length;
while(l<r){//使用二分查找小于当前数据的最大值的数组下标位置
int mid = (l+r+1)>>1;
if (q[mid] < a[i]){
l = mid;
}else{
r = mid - 1;
}
}
length = Math.max(length, r+1);
//找到位置后,因为将当前元素插入该序列后,当前序列的长度+1,故直接将q[r+1]更新即可
q[r+1] = a[i];
}
System.out.println(length);
}
}