最长上升子序列（LIS）和最长公共子序列（LCS）
相同点：子序列不要求连续，相对顺序不变即可。
目录
一、最长上升子序列（LIS）
- 给定一个长度为n 的数组，找出其中元素严格递增、且长度最长的子序列。
- 子序列不要求元素连续，只要相对顺序不变即可。
例如：[5，1，6，8，2，4，5，10]，最大递增子序列是[1，2，4，5，10]，长度为 5。
（1）经典解法1：动态规划 O (n²)
核心思路：
1、定义dp[i]：是以第 i 个元素结尾的最长递增子序列的长度
2、状态转移方程：
dp[i] = max{ dp[j] + 1 }，其中 j < i 且 nums[ j ] < nums[ i ]
找第 i 个元素之前的比nums[i]小的数，把nums[i]加到它后面，递增子序列长度加1，最后dp[i]只保留长度最大的值
3、初始时，每个元素都是长度为1的子序列。dp[i]=1
4、遍历方式：对每个数，要看它前面所有比它小的数，取最长的那个 +1
因为可能会有很多个比它小的数，但是只取长度最大的数赋值给dp[i]，这意味着dp[i]有可能不变，需要保持原来那个更大的值。等号右边的dp[i]就是之前的值。
dp[i] = Math.max(dp[i], dp[j] + 1);5、最终结果：就是返回dp数组中值最大的数，可以用一个变量记录/更新最大值，不用最后再专门遍历dp数组求最大值
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
int[] dp = new int[n];
int maxLen = 1;
// 初始化：每个元素自己是长度为1的子序列
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// 动态规划更新dp数组
//遍历每个元素，求以该元素结尾的最长子序列长度
for (int i = 1; i < n; i++) {
//遍历该元素前面的每一个元素
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
//遍历完前面的所有元素后，得到最终的dp[i],更新最大长度，以免最后还要全部遍历一遍
maxLen = Math.max(maxLen, dp[i]);
}
System.out.println(maxLen);
}
（2）优化解法2：贪心+二分查找 O (n log n)
当n很大的时候， O (n²)的动态规划会超时，这时可以用贪心 + 二分优化。
核心思路：维护一个数组talis
tails[i] ：表示长度为i+1 的递增子序列的最小可能结尾元素。目的：让结尾尽可能小，后面才能接更多数字。
- 遍历每个元素
x：- 如果
x比tails数组的最后一个元素大，直接追加到tails末尾。 - 否则，用二分找到
tails中第一个大于等于x的元素，替换它。
- 如果
- 最终
tails的长度就是最长递增子序列的长度。
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
ArrayList<Integer> tails = new ArrayList<>();
for (int x : nums) {
// 找到第一个 >= x 的位置
int idx = Collections.binarySearch(tails, x);
if (idx < 0) {
idx = -idx - 1;
}
if (idx == tails.size()) {
tails.add(x);
} else {
tails.set(idx, x);
}
}
System.out.println(tails.size());
}补充：Collections.binarySearch(list , x)返回什么？
- 二分查找——找到了 → 返回 元素在 list 中的下标（索引）；
- 没找到 → 返回 -(插入点)-1。 插入点 = list 中第一个 大于 x 的元素下标，也就是 x 应该放在哪个位置，才能保持 list 有序
举个例子跑一遍
数组：[5, 1, 6, 8, 2, 4, 5, 10]
- 5 →
tails = [5] - 1 → 替换 5 →
tails = [1] - 6 → 追加 →
tails = [1, 6] - 8 → 追加 →
tails = [1, 6, 8] - 2 → 替换 6 →
tails = [1, 2, 8] - 4 → 替换 8 →
tails = [1, 2, 4] - 5 → 追加 →
tails = [1, 2, 4, 5] - 10 → 追加 →
tails = [1, 2, 4, 5, 10]
最终 tails.size() = 5，结果正确。
二、最长公共子序列（LCS）
- 给定两个字符串
A和B，找出它们共有的、且长度最长的子序列。 - 子序列不要求字符连续，只要相对顺序不变即可。
- 例子：
A = "abcicba"B = "abdks cab"（即abdks cab）- 它们的最长公共子序列是
"abca"，长度为 4。
核心思路：动态规划（DP）/二维填表法
1、状态定义：dp[i][j]表示：字符串A前 i 个字符和字符串B前 j 个字符的最长公共子序列长度。
最终返回的结果就是：dp[n][m] n是字符串A的长度，m是字符串B的长度
注意：A[i-1]是A的第 i 个字符
2、状态转移方程：
分两种情况：
A[i-1] == B[j-1]（现在两个末尾字符一样）- 说明末尾字符可以加入到公共子序列
dp[i][j] = dp[i-1][j-1] + 1→更新当前位置的最长公共子序列dp[ i ][ j ]
A[i-1] != B[j-1]（现在两个末尾字符不一样）- 说明没法同时放进公共子序列，只能二选一
dp[i][j] = max(dp[i-1][j], dp[i][j-1])- dp[ i-1][ j ]：舍弃A最后一个字符，只看A 前 i-1 个，B 前 j 个的最长公共子序列；
- dp[ i ][ j-1]：舍弃B的最后一个字符，只看A 前 i 个，B 前 j-1 个
3、用二维dp表辅助理解：
举个例子： “abac” 和 “bcac”
| i\j | 空 | b | c | a | c |
|---|---|---|---|---|---|
| 空 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | 0 | 0 | 1 | 1 |
| b | 0 | 1 | 1 | 1 | 1 |
| a | 0 | 1 | 1 | 2 | 2 |
| c | 0 | 1 | 2 | 2 | 3 |
最终结果就是：dp[4][4]=3，最长公共子序列长度
结论：
- 字符相同：左上角，加一
- 字符不同：看上边左边，取最大
dp[i-1][j-1] dp[i-1][j]
dp[i][j-1] dp[i][j]用代码填充dp表：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String A = in.next();
String B = in.next();
int n = A.length();
int m = B.length();
// dp[i][j] 表示 A[0..i-1] 和 B[0..j-1] 的 LCS 长度
int[][] dp = new int[n + 1][m + 1];
// 填充DP表
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
System.out.println(dp[n][m]); // 输出LCS的长度
}
三、总结
LIS（一个数组）
- 看前面所有比我小的数
- 能接就接，取最长
- dp[i]=max(dp[j]+1)
LCS（两个序列）
- 相同 → 左上角 +1
- 不同 → 左 / 上取大
- 表格右下角就是结果
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
13
0- 0
已为社区贡献1条内容
所有评论(0)