题目一：最长递增子序列
给出长度为 N 的数组，找出这个数组的最长递增子序列。递增子序列是指，子序列的元素是递增的。
例如：5 1 6 8 2 4 5 10，最长递增子序列是 1 2 4 5 10
AC 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++)
array[i] = scanner.nextInt();
int res = getLIS(array, 0, n);
System.out.println(res);
}
// 求 array 的最长递增子序列的长度
public static int getLIS(int[] array, int start, int length) {
int[] ans = new int[length + 1];
ans[1] = array[start];
int maxLen = 1;
for (int i = start + 1; i < start + length; i++) {
if (array[i] > ans[maxLen]) {
ans[++maxLen] = array[i];
} else {
int pos = binarySearch(ans, 1, maxLen, array[i]);
ans[pos] = array[i];
}
}
return maxLen;
}
// 二分找到 ans 中第一个大于等于 value 的那个位置
private static int binarySearch(int[] ans, int left, int right, int value) {
int mid;
while (left < right) {
mid = (left + right) >> 1;
if (ans[mid] >= value)
right = mid;
else
left = mid + 1;
}
return left;
}
}
题目二：最长非递减子序列
小明有一袋子长方形的积木，如果一个积木 A 的长和宽都不大于另外一个积木 B 的长和宽，则积木 A 可以搭在积木 B 的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？
定义每一个长方形的长 L 和宽 W 都为正整数，并且 1 <= W <= L <= INT_MAX，袋子里面长方形的个数为 N，并且 1 <= N <= 1000000。
假如袋子里共有 5 个积木分别为 (2, 2)，(2, 4)，(3, 3)，(2, 5)，(4, 5)，则不难判断这些积木最多可以搭成 4 层，因为 (2, 2) < (2, 4) < (2, 5) < (4, 5)。
输入描述
第一行为积木的总个数 N
之后一共有 N 行，分别对应于每一个积木的宽 W 和长 L
输出描述
输出总共可以搭的层数
样例输入
5
2 2
2 4
3 3
2 5
4 5
样例输出
4
AC 代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
/**
* 思路：
* 先对长方形的宽进行一次排序，然后就变成了求长方形的长的最长非递减子序列
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] array = new int[n][2];
for (int i = 0; i < n; i++) {
array[i][0] = scanner.nextInt();
array[i][1] = scanner.nextInt();
}
Arrays.sort(array, Comparator.comparingInt(o -> o[0]));
int res = getLIS(array, 0, n);
System.out.println(res);
}
// 求 array 的最长非递减子序列的长度
public static int getLIS(int[] array, int start, int length) {
int[] ans = new int[length];
ans[0] = array[start];
int maxLen = 1;
for (int i = start + 1; i < start + length; i++) {
int pos = binarySearch(ans, 0, maxLen, array[i]);
maxLen = pos == maxLen ? maxLen + 1 : maxLen;
ans[pos] = array[i];
}
return maxLen;
}
/**
* 二分找到 ans 中第一个大于 value 的那个位置
*
* 这里 ans 中的数据范围为 [left, right)
*/
private static int binarySearch(int[] ans, int left, int right, int value) {
int mid;
while (left < right) {
mid = (left + right) >> 1;
if (ans[mid] > value)
right = mid;
else
left = mid + 1;
}
return left;
}
}
题目三：最长公共子序列
给出 1 - n 的两个排列 P1 和 P2，求它们的最长公共子序列。
输入描述
第一行是一个数 n
接下来两行，每行为 n 个数，为自然数 1 - n 的一个排列。
输出描述
一个数，代表最长公共子序列的长度
样例输入
5
3 2 1 4 5
1 2 3 4 5
样例输出
3
AC 代码
import java.util.Scanner;
/**
* 求两个序列的最长公共子序列是典型的动态规划题目，时间复杂度为 O(n^2)
*
* 但是这道题中的两个序列满足特定的条件：A B 分别是 1 - n 的两个不同的排列
*
* 这时可以将其转化为求一个序列的最长递增子序列，而求一个序列的最长递增子序列的时间
* 复杂度可以优化为 O(nlogn)
*
* 具体实现为：
* 因为序列 A B 是 1 - n 的两个不同的排列，那么 A 中出现的数字在 B 中
* 也一定存在。
* 我们可以用一个数组 pos 记录下 A 中的某个数字在序列 B 中出现的位置，那么
* 只要求得数组 pos 的最长递增子序列的长度，也就求得了 A 和 B 的最长公共子
* 序列的长度。
*
* 例如：
* A[] 1 5 4 2 3
*
* posA[] 1 2 3 4 5
*
* pos[] 5 1 2 4 3 最长递增子序列的长度为 3
*
* B[] 5 4 3 2 1
*
* 为什么会这样呢？
* 实际上我们找的并不是一个具体的数字序列，而是逻辑上的数字出现的顺序序列
*
* 如上所示，posA 代表 A 中的数字在 A 中出现的顺序，pos 代表 A 中的数字在 B 中
* 出现的顺序。
* 显然，只要找到 pos 中的一个递增子序列，那么这段递增子序列所对应 B 中的一个子序
* 列一定存在与 A 中，即找到了 A 与 B 的公共子序列。
*
* 那么只要找到了 pos 中的最长递增子序列的长度，也就找到了 A B 的最长公共子序列的长度
*
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] A = new int[n];
for (int i = 0; i < n; i++)
A[i] = scanner.nextInt();
int[] map = new int[n + 1];
for (int i = 0; i < n; i++) {
int tem = scanner.nextInt();
map[tem] = i + 1;
}
int[] pos = new int[n];
for (int i = 0; i < n; i++)
pos[i] = map[A[i]];
int res = getLIS(pos, 0, n);
System.out.println(res);
}
// 求 array 的最长递增子序列的长度
public static int getLIS(int[] array, int start, int length) {
int[] ans = new int[length + 1];
ans[1] = array[start];
int maxLen = 1;
for (int i = start + 1; i < start + length; i++) {
if (array[i] > ans[maxLen]) {
ans[++maxLen] = array[i];
} else {
int pos = binarySearch(ans, 1, maxLen, array[i]);
ans[pos] = array[i];
}
}
return maxLen;
}
// 二分找到 ans 中第一个大于等于 array[index] 的那个位置
private static int binarySearch(int[] ans, int left, int right, int value) {
int mid;
while (left < right) {
mid = (left + right) >> 1;
if (ans[mid] >= value)
right = mid;
else
left = mid + 1;
}
return left;
}
}
题目四：Array
小红有两个长度为 n 的排列 A 和 B。每个排列由 [1, n] 数组成，且里面的数字都是不同的。
现在要找到一个新的序列 C，要求这个新序列中任意两个位置 (i, j) 满足:
如果在 A 数组中 C[i] 这个数在 C[j] 的后面，那么在 B 数组中需要 C[i] 这个数在 C[j] 的前面。
请问 C 序列的长度最长为多少呢？
输入描述
第一行一个整数，表示 N。
第二行 N 个整数，表示 A 序列。
第三行 N 个整数，表示 B 序列。
满足: N <= 50000
输出描述
输出最大的长度
样例输入
5
1 2 4 3 5
5 2 3 4 1
样例输出
4
说明
最长的 C 为 [1, 3, 4, 5]
AC 代码
import java.util.Scanner;
/**
* 解题思路：
* 可以先将数组 B 倒叙为 C，这样题目就转换为了求 A 和 C 的最长公共子序列的长度
* 但如果用动态规划的话时间复杂度为 O(n^2)，题目中的 n <= 50000
* 显然会超时。
*
* 那么就可以直接使用题目二所用的方法，求得 A C 的最长公共子序列的长度
* 但是这里并没有直接将 B 倒叙，而是在对 pos 赋值的时候对 map 取负，这样就达
* 到了同样的效果。
*
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] A = new int[n];
for (int i = 0; i < n; i++)
A[i] = scanner.nextInt();
int[] map = new int[n + 1];
for (int i = 0; i < n; i++) {
int tem = scanner.nextInt();
map[tem] = i + 1;
}
int[] pos = new int[n];
// 对 map 取负值，就行当与求数组 pos 的最长上升子序列
for (int i = 0; i < n; ++i)
pos[i] = -map[A[i]];
// 接下来相当于是找 pos 的最长上升子序列，时间复杂度 O(nlogn)
int res = getLIS(pos, 0, n);
System.out.println(res);
}
// 求 array 的最长递增子序列的长度
public static int getLIS(int[] array, int start, int length) {
int[] ans = new int[length + 1];
ans[1] = array[start];
int maxLen = 1;
for (int i = start + 1; i < start + length; i++) {
if (array[i] > ans[maxLen]) {
ans[++maxLen] = array[i];
} else {
int pos = binarySearch(ans, 1, maxLen, array[i]);
ans[pos] = array[i];
}
}
return maxLen;
}
// 二分找到 ans 中第一个大于等于 array[index] 的那个位置
private static int binarySearch(int[] ans, int left, int right, int value) {
int mid;
while (left < right) {
mid = (left + right) >> 1;
if (ans[mid] >= value)
right = mid;
else
left = mid + 1;
}
return left;
}
}