最长递增子序列：动态规划与贪心解法

最长递增子序列

问题简介

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

• 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
• 严格递增 指的是对于子序列中任意相邻两个元素 a[i] < a[i+1]。

示例说明

示例 1

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,18]，因此长度为 4。

示例 2

输入：nums = [0,1,0,3,2,3] 输出：4

示例 3

输入：nums = [7,7,7,7,7,7,7] 输出：1

解题思路

方法一：动态规划（DP）—— O(n²)

思路步骤：

1. 定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
2. 初始时，每个 dp[i] = 1（每个元素自身构成长度为 1 的子序列）。
3. 对于每个 i，遍历所有 j < i：
   • 如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的子序列后，即 dp[i] = max(dp[i], dp[j] + 1)。
4. 最终答案是 max(dp[0...n-1])。

时间复杂度较高，但逻辑清晰，适合理解 LIS 本质。

方法二：贪心 + 二分查找 —— O(n log n)

思路步骤：

1. 维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素。
2. 遍历 nums 中每个元素 x：
   • 如果 x 大于 tails 的最后一个元素，则直接追加（说明可以延长当前最长子序列）。
   • 否则，在 tails 中使用二分查找找到第一个 ≥ x 的位置，并用 x 替换它（保持 tails 的性质）。
3. tails 的长度即为 LIS 的长度。

关键点：tails 数组本身不一定是真实的 LIS，但它能正确维护 LIS 的长度。

代码实现

// 方法一：动态规划 O(n²)
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);
        int res = 1;
        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);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

// 方法二：贪心 + 二分 O(n log n)
class Solution {
    public int lengthOfLIS(int[] nums) {
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        for (int x : nums) {
            int left = 0, right = tails.size();
            while (left < right) {
                int mid = (left + right) / 2;
                if (tails.get(mid) < x) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if (left == tails.size()) {
                tails.add(x);
            } else {
                tails.set(left, x);
            }
        }
        return tails.size();
    }
}

// 方法一：动态规划 O(n²)
func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    res := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        res = max(res, dp[i])
    }
    return res
}

// 方法二：贪心 + 二分 O(n log n)
func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        // 二分查找第一个 >= x 的位置
        left, right := 0, len(tails)
        for left < right {
            mid := (left + right) / 2
            if tails[mid] < x {
                left = mid + 1
            } else {
                right = mid
            }
        }
        if left == len(tails) {
            tails = append(tails, x)
        } else {
            tails[left] = x
        }
    }
    return len(tails)
}

func max  {
     a > b {
         a
    }
     b
}

示例演示

以 nums = [10,9,2,5,3,7,101,18] 为例：

方法一 DP 过程

i	nums[i]	dp[i] 计算过程	dp[i]
0	10	初始	1
1	9	无更小	1
2	2	无更小	1
3	5	2<5 → dp[3]=dp[2]+1=2	2
4	3	2<3 → dp[4]=2	2
5	7	2,5,3<7 → max(1+1,2+1,2+1)=3	3
6	101	… → 4	4
7	18	… → 4	4

最终结果：4

方法二 tails 过程

x	tails（变化）
10	[10]
9	[9]
2	[2]
5	[2,5]
3	[2,3]
7	[2,3,7]
101	[2,3,7,101]
18	[2,3,7,18]

最终长度：4

答案有效性证明

方法一（DP）

• 正确性：dp[i] 明确定义为以 i 结尾的 LIS 长度，通过枚举所有可能前驱 j，确保状态转移完整。
• 最优子结构：LIS 具有最优子结构性质，局部最优可推导全局最优。

方法二（贪心 + 二分）

• 关键引理：tails 数组始终保持严格递增（可用反证法证明）。
• 替换策略：用更小的值替换 tails 中的元素，不会影响已有的 LIS 长度，但为后续扩展提供更大可能性。
• 长度不变性：每次只修改 tails 中某个位置的值，或在末尾追加，因此 len(tails) 始终等于当前 LIS 长度。

虽然 tails 不一定是真实子序列，但其长度等于 LIS 长度，这是该算法的核心洞察。

复杂度分析

方法	时间复杂度	空间复杂度	适用场景
动态规划	O(n²)	O(n)	n ≤ 10⁴
贪心 + 二分	O(n log n)	O(n)	n ≤ 10⁵ 或更高

在 LeetCode 测试用例中，两种方法均可通过，但 O(n log n) 更优。

问题总结

• 核心思想：LIS 是经典动态规划问题，但可通过贪心策略 + 二分优化提升效率。
• 关键技巧：
  • DP 状态定义要清晰（以 i 结尾）。
  • 贪心法中维护'最小末尾'数组 tails 是突破口。
• 扩展思考：
  • 如何输出具体的 LIS 序列？（需记录路径，DP 可行，贪心法较难）
  • 若允许非严格递增（≤），如何修改？（二分查找条件改为 <=）

掌握这两种解法，不仅能解决本题，也为处理其他子序列类问题打下基础。