题目描述
最长上升子序列I的数据量增多的版本
算法
思路:在数组q中形成最长的上升子序列
过程:遇到一个元素target时,在数组q中查找第一个大于或等于target的元素的位置pos,并且替换pos所在的元素cur。
解释:因为cur>=target, 后续元素next>cur, 肯定大于target。
举例:3 1 2 1 8 5 6
1. 空
q数组:3
2. 1<3
q数组:1
3. 2>1
q数组:1 2
4. 1>=数组q的1,替换数组q的1
q数组:1 2
5. 8>2
q数组:1 2 8
6. 5<8
q数组:1 2 5
7. 6>5
q数组:1 2 5 6
具体实现(1) (2)
(1)在q数组中找到小于a[i]的元素位置
从第一个位置开始使用
import java.util.*;
public class Main {
static int N = 100010;
static int[] a = new int[N];
static int[] q = new int[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i=0; i<n; i++) a[i] = scanner.nextInt();
int len = 0;
for (int i=0; i<n; i++) {
int l = 0;
int r = len;
// 找到比a[i]第一个小的元素
while (l < r) {
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);
}
}
(2)在q数组中找到大于等于a[i]的元素位置
使用了第0个位置
import java.util.*;
public class Main {
static int N = 100010;
static int[] a = new int[N];
static int[] q = new int[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i=0; i<n; i++) a[i] = scanner.nextInt();
int len = 0;
for (int i=0; i<n; i++) {
int l = 0;
int r = len;
// 找到第一个大于等于a[i]的元素
while (l < r) {
int mid = (l + r) >> 1;
if (q[mid] >= a[i]) r = mid;
else l = mid + 1;
}
if (q[r] >= a[i] || q[r] == 0) q[r] = a[i];
else q[++r] = a[i];
len = Math.max(len, r);
}
System.out.println(len+1);
}
}