几种子序列问题
集中子序列问题
最长上升子序列:只有一个数组,求最长上升子序列。定义 f[i] 为以 arr[i] 为结尾的最长上升子序列。状态转移是从 [1,…j - 1] 找后面可以接上 arr[i] 的数
有 O(n^2) 的朴素做法,也有 O(n log n) 的贪心二分解法
O(n^2) 做法
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
// 定义 f[i] 为以第 i 个元素为结尾的最长长度
int[] f = new int[n + 1];
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) f[i] = Math.max(f[i], f[j] + 1);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = Math.max(ans, f[i]);
System.out.println(ans);
}
}
O(n log n)
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
// 反链定理?Dilworth 定理:最长上升子序列的长度 = 最小用多少个「下降」子序列覆盖掉整个数组
// 本题与 1010. 拦截导弹 的第二问 是对偶问题
// 动态规划数组,f[i] 记录的是以 a[i] 为结尾的最长上升子序列的长度
int[] f = new int[n + 1];
// 贪心数组:q[len] = x 代表长度为 len 的最长上升子序列的「最小结尾元素」为 x
int[] q = new int[n + 1];
int ans = 1;
Arrays.fill(q, Integer.MAX_VALUE);
for (int i = 1; i <= n; i++) {
int x = a[i];
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (q[mid] < x) {
l = mid;
} else {
r = mid - 1;
}
}
int len = r + 1;
f[i] = len;
q[len] = Math.min(q[len], x);
ans = Math.max(ans, f[i]);
}
System.out.println(ans);
}
}
最长公共子序列:有两个数组,找最长公共子序列。定义 f[i][j] 为考虑 a 的前 i 个字符,b 的前 j 个字符的最长公共子序列。状态转移考虑是否包含 a[i] 和 b[j] 的四种情况
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
String a = sc.next(), b = sc.next();
a = " " + a;
b = " " + b;
char[] ca = a.toCharArray();
char[] cb = b.toCharArray();
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]);
if (ca[i] == cb[j]) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
System.out.println(f[n][m]);
}
}
最长公共上升子序列:有两个数组,找最长公共上升子序列。定义 f[i][j] 为考虑 a 的前 i 个字符,b 的前 j 个字符,且以 b[j] 为结尾的最长公共上升子序列。状态转移为考虑 a[i] 是否包含在子序列中。如果 a[i] 不包含,则是 f[i][j] = f[i - 1][j],如果 a[i] 包含,首先必然有 a[i] == b[j],再考虑 b[j] 的前一位是什么,从 [1, … , j - 1] 去枚举 k,找到符合 b[k] < b[j] 的,状态转移为 f[i - 1][k] + 1,在所有的方案中取 max。
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n + 1], b = new int[n + 1];
for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
for (int i = 1; i <= n; i++) b[i] = sc.nextInt();
int[][] f = new int[n + 1][n + 1];
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) {
f[i][j] = Math.max(f[i][j], 1);
for (int k = 1; k < j; k++) {
if (b[k] < b[j]) f[i][j] = Math.max(f[i][j], f[i - 1][k] + 1);
}
}
ans = Math.max(ans, f[i][j]);
}
}
System.out.println(ans);
}
}