最长递增子序列(LIS)问题详解

最长递增子序列LIS问题详解

• • 一、问题定义与核心特征
  • • 1.1 问题描述
    • 1.2 核心特征
  • 二、基础解法：动态规划（DP）
  • • 2.1 解法思路
    • 2.2 Java代码实现
    • 2.3 复杂度分析
  • 三、优化解法：二分查找+贪心
  • • 3.1 核心思路
    • 3.2 二分查找的作用
    • 3.3 Java代码实现
    • • 代码说明：
    • 3.4 复杂度分析
  • 四、变种问题与拓展
  • • 4.1 最长非递减子序列
    • 4.2 输出具体的最长递增子序列
    • 4.3 二维LIS问题（信封嵌套）
  • 五、LIS的实际应用场景
  • 六、两种解法的对比与选择
  • 总结

最长递增子序列（Longest Increasing Subsequence，简称LIS）是动态规划领域的经典问题，它看似简单——在一个无序数组中找到最长的严格递增子序列（子序列无需连续），但背后隐藏着从暴力到高效的多种解法思路。本文我将系统解析LIS问题的核心逻辑，从基础的动态规划到优化的“二分查找+贪心”解法，并结合代码实现、复杂度分析及变种拓展全面解读。

一、问题定义与核心特征

1.1 问题描述

给定一个整数数组nums，找到其中最长的严格递增子序列的长度。

• 子序列：由数组中部分元素组成，元素顺序与原数组一致（无需连续）。
• 严格递增：子序列中每个元素都大于前一个元素（如[2,5,7]是递增子序列，[2,2,3]不是）。

示例：

• 输入：nums = [10,9,2,5,3,7,101,18]
• 输出：4（最长递增子序列为[2,3,7,18]或[2,5,7,101]）

1.2 核心特征

• 无连续性要求：子序列元素在原数组中可间隔存在（区别于“最长递增子数组”）。
• 严格递增：需满足nums[i] < nums[j]（i < j），若允许相等则为“最长非递减子序列”。
• 多解性：可能存在多个长度相同的最长子序列，但问题通常只要求返回长度。

二、基础解法：动态规划（DP）

动态规划是解决LIS问题的基础方法，核心思路是通过“以每个元素为结尾的最长子序列长度”推导全局最优。

2.1 解法思路

1. 定义状态：
   设dp[i]表示“以nums[i]为结尾的最长递增子序列的长度”。
   （核心：子序列必须包含nums[i]，且nums[i]是子序列的最后一个元素）

2. 递推关系：
   对于每个i（当前元素），遍历所有j < i（前驱元素）：

   • 若nums[j] < nums[i]（满足递增），则dp[i]可由dp[j] + 1更新（在前驱子序列后添加nums[i]）。
   • 取所有符合条件的dp[j] + 1的最大值，即：
     dp[i] = max(dp[j] + 1) （j < i 且 nums[j] < nums[i]）
   • 若没有符合条件的j（即nums[i]比所有前驱都小），则dp[i] = 1（自身为长度1的子序列）。

3. 边界条件：
   所有dp[i]初始化为1（每个元素自身都是长度为1的子序列）。

4. 结果计算：
   全局最长递增子序列长度为dp数组中的最大值。

2.2 Java代码实现

import java.util.Arrays;public class LIS_DP { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); // 初始化：每个元素自身是长度1的子序列 int maxLen = 1; // 最小长度为1 for (int i = 1; i < n; i++) { // 遍历所有前驱元素j for (int j = 0; j < i; j++) { // 若j位置元素小于i位置，尝试更新dp[i] if (nums[j] < nums[i]) {  dp[i] = Math.max(dp[i], dp[j] + 1); } } // 更新全局最大值 maxLen = Math.max(maxLen, dp[i]); } return maxLen; } public static void main(String[] args) { LIS_DP solution = new LIS_DP(); int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; System.out.println(solution.lengthOfLIS(nums)); // 输出4 }}

2.3 复杂度分析

• 时间复杂度： O ( n 2 ) O(n^2) O(n2)。外层循环遍历n个元素，内层循环对每个元素遍历其所有前驱（平均n/2次），总操作次数为 n × n / 2 = O ( n 2 ) n \\times n/2 = O(n^2) n×n/2=O(n2)。
• 空间复杂度：$O(n)$。需要dp数组存储n个状态。

适用场景：数组长度较小（n ≤ 1000）时，该方法简单直观，易于实现。

三、优化解法：二分查找+贪心

当数组长度较大（如n > 10^4）时， O( n 2 ) O(n^2) O(n2)的动态规划解法会超时。“二分查找+贪心”解法通过优化状态维护方式，将时间复杂度降至$O(n\log n)$，是LIS问题的最优解法。

3.1 核心思路

贪心思想：维护一个尽可能小的“递增子序列尾部元素”。尾部元素越小，后续能添加的元素就越多，越容易形成更长的子序列。

例如：

• 对于nums = [2,5,3,7]，若已有的子序列尾部是[2,5]，当遇到3时，可将5替换为3（得到[2,3]）——虽然当前长度不变，但尾部更小，后续可添加7形成[2,3,7]（比[2,5,7]更优）。

具体步骤：

1. 定义一个列表tails，tails[i]表示“长度为i+1的递增子序列的最小尾部元素”。
2. 遍历数组nums，对每个元素x：
   • 若x大于tails的最后一个元素，直接加入tails（子序列长度+1）。
   • 否则，在tails中找到第一个大于等于x的元素，用x替换它（维持尾部最小化）。
3. 最终tails的长度即为LIS的长度。

3.2 二分查找的作用

tails是严格递增的（因为每次添加的元素都大于尾部，替换的元素也保证了递增性），因此可通过二分查找快速定位“第一个大于等于x的元素”，时间复杂度从$O(n)$降至$O(\log n)$。

3.3 Java代码实现

import java.util.ArrayList;import java.util.List;public class LIS_BinarySearch { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } List<Integer> tails = new ArrayList<>(); for (int x : nums) { // 二分查找：找到tails中第一个 >= x的元素索引 int left = 0, right = tails.size(); while (left < right) { int mid = left + (right - left) / 2; if (tails.get(mid) < x) {  left = mid + 1; // x更大，继续向右找 } else {  right = mid; // 可能找到，缩小右边界 } } // 若left等于长度，说明x是最大的，直接添加 if (left == tails.size()) { tails.add(x); } else { // 否则替换对应位置的元素 tails.set(left, x); } } return tails.size(); } public static void main(String[] args) { LIS_BinarySearch solution = new LIS_BinarySearch(); int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; System.out.println(solution.lengthOfLIS(nums)); // 输出4 }}

代码说明：

• tails始终保持严格递增，例如输入[10,9,2,5,3,7,101,18]时，tails的变化过程为：
  [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
  最终长度为4，与预期结果一致。

3.4 复杂度分析

• 时间复杂度：$O(n\log n)$。遍历数组n次，每次二分查找操作耗时$O(\log k)$（k为当前tails长度，最大为n），总复杂度为$n\times \log n=O(n\log n)$。
• 空间复杂度：$O(n)$。tails列表最坏情况下存储n个元素（数组完全递增时）。

适用场景：数组长度较大（n ≥ 10^4）时，该方法效率显著优于动态规划。

四、变种问题与拓展

4.1 最长非递减子序列

问题：允许子序列元素相等（即nums[i] ≤ nums[j]），求最长子序列长度。
解法：修改二分查找条件——将“找到第一个大于等于x的元素”改为“找到第一个大于x的元素”（允许替换相等元素）。
代码调整：

// 非递减子序列的二分查找条件if (tails.get(mid) <= x) { // 原条件为 < x left = mid + 1;} else { right = mid;}

4.2 输出具体的最长递增子序列

基础解法和优化解法均只能得到长度，若需输出具体子序列，需结合动态规划记录前驱：

1. 用dp数组记录长度，prev数组记录每个元素的前驱索引。
2. 找到dp数组最大值对应的索引，通过prev回溯得到子序列。

示例代码：

public int[] getLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; int[] prev = new int[n]; Arrays.fill(dp, 1); Arrays.fill(prev, -1); int maxLen = 1, 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] > maxLen) { maxLen = dp[i]; maxIndex = i; // 记录最长子序列的结尾索引 } } // 回溯构建子序列 int[] lis = new int[maxLen]; int index = maxLen - 1; while (maxIndex != -1) { lis[index--] = nums[maxIndex]; maxIndex = prev[maxIndex]; } return lis;}

4.3 二维LIS问题（信封嵌套）

问题：给定n个信封(w, h)，若w1 < w2且h1 < h2则可嵌套，求最多嵌套层数（本质是二维LIS）。
解法：

1. 按宽度w升序排序（宽度相等时按高度h降序，避免同宽信封嵌套）。
2. 对高度h求LIS，长度即为最大嵌套层数。

五、LIS的实际应用场景

1. 任务调度：安排依赖关系的任务，找到最长的连续执行序列。
2. 导弹拦截：拦截导弹的高度需严格递增，求最多拦截数量。
3. 数据可视化：在时序数据中找到最长的增长趋势段。
4. 算法优化：作为其他问题的子步骤（如最长递增子序列的个数、最大上升子序列和等）。

六、两种解法的对比与选择

解法 时间复杂度 空间复杂度 优势场景 核心思想 动态规划 O ( n 2 ) O(n^2) O(n2) $O(n)$ 数组短（n ≤ 1000）、需输出子序列 以每个元素为结尾的子序列长度 二分查找+贪心 $O(n\log n)$ $O(n)$ 数组长（n ≥ 10^4）、仅需长度 维护最小尾部元素，贪心优化

总结

LIS问题是动态规划与贪心思想结合的经典案例，从 O( n 2 ) O(n^2) O(n2)的基础解法到$O(n\log n)$的优化解法，体现了“状态优化”的核心思路——通过更高效的状态维护（如tails列表）减少冗余计算。

掌握LIS问题的关键在于：

1. 理解动态规划的状态定义（以每个元素为结尾的子序列长度）；
2. 掌握“二分查找+贪心”的优化逻辑（最小尾部元素的维护）；
3. 能根据问题需求（长度/具体子序列、数组大小）选择合适解法。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～