引言
最长递增子序列（Longest Increasing Subsequence，LIS）是算法竞赛和面试中的经典问题。给定一个整数序列，找出其中最长的严格递增子序列的长度。本文将用Java实现两种解法：基础动态规划（O(n²)）和基于二分查找的贪心优化（O(n log n)），帮助读者深入理解状态转移与单调性优化技巧。
问题定义
输入：一个长度为 n 的整数数组 nums。
输出：nums 的最长严格递增子序列的长度。
示例：
– 输入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
– 输出：4
– 解释：最长递增子序列为 [2, 3, 7, 101]
方法一：动态规划（O(n²)）
核心思想
设 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。对于每个位置 i，遍历所有前面的位置 j（j < i），如果 nums[j] < nums[i]，则 dp[i] 可以从 dp[j] 转移而来。
状态转移方程：
dp[i] = max(dp[j] + 1) 对于所有 j < i 且 nums[j] < nums[i]
初始状态：dp[i] = 1（每个元素本身构成长度为1的递增子序列）
Java实现
public class LIS_DynamicProgramming {
/**
* 动态规划解法，时间复杂度 O(n²)，空间复杂度 O(n)
* @param nums 输入数组
* @return 最长递增子序列长度
*/
public static int lengthOfLIS_DP(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
// dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
int[] dp = new int[n];
// 初始化：每个元素自身构成长度为1的子序列
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
int maxLength = 1;
// 遍历每个位置作为子序列结尾
for (int i = 1; i < n; i++) {
// 检查所有前面的位置，寻找可以接在后面的递增序列
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
// 如果 nums[j] < nums[i]，则可以将 nums[i] 接到以 nums[j] 结尾的序列后面
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 更新全局最大值
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
/**
* 同时返回具体的LIS序列（用于调试和理解）
*/
public static int[] getLIS_Sequence(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]; // 记录前驱节点，用于重构序列
for (int i = 0; i < n; i++) {
dp[i] = 1;
prev[i] = -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;
}
}
// 重构LIS序列
int[] lis = new int[maxLength];
int idx = maxLength - 1;
int cur = maxIndex;
while (cur != -1) {
lis[idx--] = nums[cur];
cur = prev[cur];
}
return lis;
}
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("输入数组: [10, 9, 2, 5, 3, 7, 101, 18]");
System.out.println("DP解法LIS长度: " + lengthOfLIS_DP(nums));
int[] seq = getLIS_Sequence(nums);
System.out.print("LIS序列: ");
for (int x : seq) {
System.out.print(x + " ");
}
System.out.println();
}
}
方法二：二分优化（O(n log n)）
核心思想
维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的所有递增子序列中，结尾元素的最小值。这个数组一定是严格递增的，因此可以用二分查找来优化查找过程。
关键观察：
– 如果当前元素 x 大于 tails 的最后一个元素，直接追加，LIS长度+1
– 否则，在 tails 中找到第一个大于等于 x 的位置，用 x 替换它
这样 tails 数组始终保持有序，可以用 Arrays.binarySearch 或自定义二分查找。
Java实现
import java.util.Arrays;
public class LIS_BinarySearch {
/**
* 二分优化解法，时间复杂度 O(n log n)，空间复杂度 O(n)
* @param nums 输入数组
* @return 最长递增子序列长度
*/
public static int lengthOfLIS_Binary(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
// tails[i] 表示长度为 i+1 的递增子序列的最小结尾元素
int[] tails = new int[n];
int size = 0; // 当前LIS的长度
for (int num : nums) {
// 在 tails[0..size) 中找到第一个 >= num 的位置
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1; // 在右半部分继续查找
} else {
right = mid; // 在左半部分继续查找（包括mid）
}
}
// left 就是 num 应该放置的位置
tails[left] = num;
// 如果 num 比所有已存在的结尾元素都大，则扩展LIS长度
if (left == size) {
size++;
}
}
return size;
}
/**
* 使用 Java 内置二分查找的简化版本
*/
public static int lengthOfLIS_BuiltIn(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
int idx = Arrays.binarySearch(tails, 0, size, num);
// binarySearch 返回非负表示找到，返回负数表示应该插入的位置
if (idx < 0) {
idx = -(idx + 1);
}
tails[idx] = num;
if (idx == size) {
size++;
}
}
return size;
}
/**
* 二分优化同时获取具体的LIS序列
*/
public static int[] getLIS_Binary(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] tails = new int[n]; // tails值
int[] tailIndices = new int[n]; // tails中每个位置对应的原数组下标
int[] prev = new int[n]; // 每个元素的前驱
Arrays.fill(prev, -1);
int size = 0;
for (int i = 0; i < n; i++) {
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = nums[i];
tailIndices[left] = i;
// 记录前驱：如果 left > 0，则前驱是 tails[left-1] 对应的原数组下标
if (left > 0) {
prev[i] = tailIndices[left - 1];
}
if (left == size) {
size++;
}
}
// 重构序列
int[] lis = new int[size];
int cur = tailIndices[size - 1];
for (int i = size - 1; i >= 0; i--) {
lis[i] = nums[cur];
cur = prev[cur];
}
return lis;
}
public static void main(String[] args) {
int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
int[] nums2 = {0, 1, 0, 3, 2, 3};
int[] nums3 = {7, 7, 7, 7, 7, 7, 7};
System.out.println("数组 [10,9,2,5,3,7,101,18] LIS长度: " + lengthOfLIS_Binary(nums1));
System.out.println("数组 [0,1,0,3,2,3] LIS长度: " + lengthOfLIS_Binary(nums2));
System.out.println("数组 [7,7,7,7,7,7,7] LIS长度: " + lengthOfLIS_Binary(nums3));
int[] seq = getLIS_Binary(nums1);
System.out.print("LIS序列: ");
for (int x : seq) {
System.out.print(x + " ");
}
System.out.println();
}
}
两种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 动态规划 | O(n²) | O(n) | 需要获取具体序列，n ≤ 10⁴ |
| 二分优化 | O(n log n) | O(n) | 只需长度，或 n 很大（可达 10⁵ ~ 10⁶） |
复杂度分析
动态规划法：
– 时间复杂度：O(n²)，双重循环遍历所有 (j, i) 对
– 空间复杂度：O(n)，dp 数组和 prev 数组
二分优化法：
– 时间复杂度：O(n log n)，每个元素进行一次二分查找
– 空间复杂度：O(n)，tails 数组
扩展与变体
- 最长递减子序列（LDS）：将数组取反或改变比较方向即可
- 最长非递减子序列：将严格小于
<改为<= - 二维LIS：如信封嵌套问题，先按一维排序，再对另一维求LIS
- LIS数量：统计最长递增子序列的个数，需要额外维护 count 数组
总结
最长递增子序列问题是理解动态规划与贪心二分优化的绝佳切入点。O(n²) 的DP解法直观易懂，而 O(n log n) 的二分优化则展示了如何利用问题的单调性来加速求解。在实际应用中，根据数据规模选择合适的算法至关重要。掌握这两种方法，也为后续学习更复杂的动态规划优化技巧（如线段树优化DP、树状数组优化DP）打下了坚实基础。
