最长递增子序列（Longest Increasing Subsequence，简称LIS）是算法领域中经典的动态规划问题。给定一个整数序列，找出一个最长的子序列，使得子序列中的元素严格递增。子序列不要求连续，但要求相对顺序不变。本文将用Java实现两种解法：O(n²)的经典动态规划，以及O(n log n)的二分查找优化方案。
问题定义
给定一个长度为 n 的数组 nums，需要找到其中最长的严格递增子序列的长度。例如：
- 输入：
[10, 9, 2, 5, 3, 7, 101, 18] - 输出：
4 - 解释：最长递增子序列为
[2, 3, 7, 101]
这个问题在实际中有广泛应用，比如数据压缩中的游程编码优化、生物信息学中的DNA序列比对，以及版本控制系统中的diff算法等。
O(n²) 动态规划解法
核心思想
定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。对于每个位置 i，遍历其之前的所有位置 j（0 <= j < i），如果 nums[j] < nums[i]，则 nums[i] 可以接在 nums[j] 后面形成更长的递增子序列。
状态转移方程为：
dp[i] = max(dp[i], dp[j] + 1) 其中 0 <= j < i 且 nums[j] < nums[i]
初始状态：dp[i] = 1，每个元素本身可以构成长度为1的递增子序列。
Java实现
/**
* O(n²) 动态规划求解最长递增子序列
*/
public class LISDynamicProgramming {
/**
* 计算最长递增子序列的长度
* @param nums 输入数组
* @return 最长递增子序列的长度
*/
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
// dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
int[] dp = new int[n];
// 初始化：每个元素自身构成长度为1的递增子序列
java.util.Arrays.fill(dp, 1);
int maxLength = 1;
// 遍历每个位置作为子序列结尾
for (int i = 1; i < n; i++) {
// 检查 i 之前的所有位置
for (int j = 0; j < i; j++) {
// 如果 nums[j] < nums[i]，则 nums[i] 可以接在 nums[j] 后面
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 更新全局最大值
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
/**
* 同时返回最长递增子序列的具体序列
*/
public int[] getLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] dp = new int[n];
int[] prev = new int[n]; // 记录前驱节点，用于重构序列
java.util.Arrays.fill(dp, 1);
java.util.Arrays.fill(prev, -1);
int maxLength = 1;
int maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j; // 记录前驱
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
maxIndex = i;
}
}
// 重构最长递增子序列
int[] result = new int[maxLength];
int index = maxLength - 1;
while (maxIndex != -1) {
result[index--] = nums[maxIndex];
maxIndex = prev[maxIndex];
}
return result;
}
public static void main(String[] args) {
LISDynamicProgramming solution = new LISDynamicProgramming();
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("输入数组: " + java.util.Arrays.toString(nums));
System.out.println("LIS长度: " + solution.lengthOfLIS(nums));
System.out.println("LIS序列: " + java.util.Arrays.toString(solution.getLIS(nums)));
}
}
复杂度分析
- 时间复杂度：O(n²)，双重循环遍历所有
(i, j)对 - 空间复杂度：O(n)，
dp数组和prev数组的空间
O(n log n) 二分查找优化
核心思想
观察动态规划解法，内层循环的本质是在 dp[0...i-1] 中找到一个满足 nums[j] < nums[i] 且 dp[j] 最大的位置。这个查找过程可以用更高效的数据结构来优化。
优化的关键在于维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素。例如，如果 tails[2] = 5，表示所有长度为3的递增子序列中，末尾元素最小的是5。
为什么维护最小末尾元素？因为更小的末尾元素更容易被后续元素接上，从而延长子序列。
当处理一个新元素 nums[i] 时：
1. 如果 nums[i] 比 tails 中所有元素都大，说明可以延长最长子序列
2. 否则，用 nums[i] 替换 tails 中第一个大于等于 nums[i] 的元素
由于 tails 数组始终保持有序，查找和替换过程可以用二分查找在 O(log n) 内完成。
Java实现
/**
* O(n log n) 二分查找优化求解最长递增子序列
*/
public class LISBinarySearch {
/**
* 计算最长递增子序列的长度（二分优化版）
* @param nums 输入数组
* @return 最长递增子序列的长度
*/
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
// tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素
int[] tails = new int[n];
int size = 0; // 当前最长递增子序列的长度
for (int num : nums) {
// 二分查找：找到 tails 中第一个 >= num 的位置
int left = 0;
int right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1; // num 可以接在这个子序列后面
} else {
right = mid; // 需要替换的位置在左侧
}
}
// left 就是插入位置
tails[left] = num;
// 如果 num 比所有 tails 元素都大，则扩展最长长度
if (left == size) {
size++;
}
}
return size;
}
/**
* 同时返回最长递增子序列的具体序列（需要额外维护）
*/
public int[] getLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] tails = new int[n];
int[] tailsIndices = new int[n]; // 记录 tails 中每个位置对应的原始索引
int[] prev = new int[n]; // 前驱数组，用于重构序列
java.util.Arrays.fill(prev, -1);
int size = 0;
for (int i = 0; i < n; i++) {
int num = nums[i];
int left = 0;
int right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
tailsIndices[left] = i;
// 设置前驱：如果 left > 0，则前驱是 tails 中前一个位置的索引
if (left > 0) {
prev[i] = tailsIndices[left - 1];
}
if (left == size) {
size++;
}
}
// 从最后一个 tails 元素开始回溯
int[] result = new int[size];
int index = tailsIndices[size - 1];
for (int i = size - 1; i >= 0; i--) {
result[i] = nums[index];
index = prev[index];
}
return result;
}
public static void main(String[] args) {
LISBinarySearch solution = new LISBinarySearch();
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("输入数组: " + java.util.Arrays.toString(nums));
System.out.println("LIS长度 (O(n log n)): " + solution.lengthOfLIS(nums));
System.out.println("LIS序列 (O(n log n)): " + java.util.Arrays.toString(solution.getLIS(nums)));
// 测试更多用例
int[] nums2 = {0, 1, 0, 3, 2, 3};
System.out.println("\\n输入数组: " + java.util.Arrays.toString(nums2));
System.out.println("LIS长度: " + solution.lengthOfLIS(nums2));
System.out.println("LIS序列: " + java.util.Arrays.toString(solution.getLIS(nums2)));
int[] nums3 = {7, 7, 7, 7, 7, 7};
System.out.println("\\n输入数组: " + java.util.Arrays.toString(nums3));
System.out.println("LIS长度: " + solution.lengthOfLIS(nums3));
}
}
复杂度分析
- 时间复杂度：O(n log n)，每个元素进行一次二分查找
- 空间复杂度：O(n)，
tails数组和辅助数组的空间
两种方法对比
| 指标 | O(n²) 动态规划 | O(n log n) 二分优化 |
|---|---|---|
| 时间复杂度 | O(n²) | O(n log n) |
| 空间复杂度 | O(n) | O(n) |
| 核心思想 | 枚举所有子问题 | 维护最小末尾元素 |
| 适用场景 | n < 10⁴ | n 可达 10⁵ ~ 10⁶ |
| 代码难度 | 直观易懂 | 需要理解 tails 数组含义 |
对于面试和竞赛场景，二分优化版本是更优的选择；而对于学习和理解动态规划思想，经典版本更有助于建立直觉。
完整项目结构
src/
├── LISDynamicProgramming.java # O(n²) 动态规划实现
├── LISBinarySearch.java # O(n log n) 二分优化实现
└── LISTest.java # 单元测试与性能对比
/**
* 单元测试与性能对比
*/
public class LISTest {
public static void main(String[] args) {
// 功能测试
testFunctional();
// 性能对比
testPerformance();
}
private static void testFunctional() {
int[][] testCases = {
{10, 9, 2, 5, 3, 7, 101, 18}, // 预期: 4
{0, 1, 0, 3, 2, 3}, // 预期: 4
{7, 7, 7, 7, 7, 7}, // 预期: 1 (严格递增)
{1, 3, 6, 7, 9, 4, 10, 5, 6}, // 预期: 6
{}, // 预期: 0
{5} // 预期: 1
};
LISDynamicProgramming dpSol = new LISDynamicProgramming();
LISBinarySearch bsSol = new LISBinarySearch();
System.out.println("===== 功能测试 =====");
for (int[] nums : testCases) {
int dpResult = dpSol.lengthOfLIS(nums);
int bsResult = bsSol.lengthOfLIS(nums);
boolean pass = dpResult == bsResult;
System.out.printf("数组: %-30s | DP: %d | BS: %d | %s%n",
java.util.Arrays.toString(nums), dpResult, bsResult,
pass ? "✓" : "✗");
}
}
private static void testPerformance() {
int n = 10000;
int[] largeArray = new int[n];
java.util.Random random = new java.util.Random(42);
for (int i = 0; i < n; i++) {
largeArray[i] = random.nextInt(100000);
}
LISDynamicProgramming dpSol = new LISDynamicProgramming();
LISBinarySearch bsSol = new LISBinarySearch();
System.out.println("\\n===== 性能对比 (n=" + n + ") =====");
long start1 = System.currentTimeMillis();
int dpResult = dpSol.lengthOfLIS(largeArray);
long time1 = System.currentTimeMillis() - start1;
System.out.printf("O(n²) 动态规划: 结果=%d, 耗时=%dms%n", dpResult, time1);
long start2 = System.currentTimeMillis();
int bsResult = bsSol.lengthOfLIS(largeArray);
long time2 = System.currentTimeMillis() - start2;
System.out.printf("O(n log n) 二分优化: 结果=%d, 耗时=%dms%n", bsResult, time2);
System.out.printf("性能提升: %.2f 倍%n", (double) time1 / time2);
}
}
扩展思考
-
非严格递增：将条件
nums[j] < nums[i]改为nums[j] <= nums[i]，二分查找中tails[mid] < num改为tails[mid] <= num。 -
最长递减子序列：将数组取反或改变比较方向即可。
-
最长摆动子序列：结合递增和递减的状态转移。
-
二维LIS：将一维扩展为二维偏序关系，通常需要先按一维排序再用LIS。
总结
最长递增子序列问题展示了算法优化的经典路径：从直观的 O(n²) 动态规划出发，通过分析问题结构（维护最小末尾元素），将时间复杂度优化到 O(n log n)。这种从暴力到优化的思考方式，是解决算法问题的通用方法论。
二分优化版本虽然代码更短，但理解其正确性需要仔细思考 tails 数组的维护逻辑。建议读者先掌握经典DP版本，再深入理解优化版本的精妙之处。
