最長遞增子序列（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; // 最小長度為1for (int i = 1; i < n; i++) {// 遍歷所有前驅元素jfor (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)$。外層循環遍歷n個元素，內層循環對每個元素遍歷其所有前驅（平均n/2次），總操作次數為$n\times n/2=O(n^2)$。
• 空間復雜度：$O(n)$。需要dp數組存儲n個狀態。

適用場景：數組長度較小（n ≤ 1000）時，該方法簡單直觀，易于實現。

三、優化解法：二分查找+貪心

當數組長度較大（如n > 10^4）時，$O(n^2)$的動態規劃解法會超時。“二分查找+貪心”解法通過優化狀態維護方式，將時間復雜度降至$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) { // 原條件為 < xleft = 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)$	數組短（n ≤ 1000）、需輸出子序列	以每個元素為結尾的子序列長度
二分查找+貪心	$O(n\log n)$	$O(n)$	數組長（n ≥ 10^4）、僅需長度	維護最小尾部元素，貪心優化

總結

LIS問題是動態規劃與貪心思想結合的經典案例，從$O(n^2)$的基礎解法到$O(n\log n)$的優化解法，體現了“狀態優化”的核心思路——通過更高效的狀態維護（如tails列表）減少冗余計算。

掌握LIS問題的關鍵在于：

1. 理解動態規劃的狀態定義（以每個元素為結尾的子序列長度）；
2. 掌握“二分查找+貪心”的優化邏輯（最小尾部元素的維護）；
3. 能根據問題需求（長度/具體子序列、數組大小）選擇合適解法。

That’s all, thanks for reading~~
覺得有用就點個贊、收進收藏夾吧！關注我，獲取更多干貨～