AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
gongjin
,
2023-02-10 16:59:48
,
所有人可见
,
阅读 103
优化版的最长上升子序列
import java.util.Scanner;
class Main {
static int N = 100010;
static int n;
static int[] a = new int[N];
static int[] q = new int[N];
/**
* q存储的是长度为i的上升子序列结尾的最小值
* 例如 12543
* 1
* 12
* 125
* 124
* 123
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
int len = 0;
q[0] = (int) -2e9;
for (int i = 0; i < n; i++) {
if (a[i] > q[len]) {
q[++len] = a[i];
continue;
}
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (q[mid] < a[i]) {
l = mid;
} else {
r = mid - 1;
}
}
q[l + 1] = a[i];
}
System.out.println(len);
}
}