动态规划4：最长递增子序列问题

引言

在动态规划系列的前三篇文章中，我们分别学习了爬楼梯问题、最长公共子序列和01背包问题。今天我们将探讨另一个动态规划的经典问题——最长递增子序列（Longest Increasing Subsequence，LIS）。

最长递增子序列问题不仅是动态规划的核心问题之一，更是算法优化思想的绝佳体现。从朴素的O(n²)动态规划解法，到巧妙的O(nlogn)优化算法，这个问题展现了算法设计的精妙之处。

问题定义

什么是递增子序列？

递增子序列：从原数组中按照原有顺序选取若干元素，使得这些元素严格递增。

注意几个关键点：

保持原有顺序：不能改变元素在原数组中的相对位置
严格递增：后面的元素必须大于前面的元素
不要求连续：子序列的元素在原数组中可以不相邻

最长递增子序列问题

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

经典例题：LeetCode 300. 最长递增子序列

示例 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
解释：最长递增子序列是 [0,1,2,3]，因此长度为 4。

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
解释：最长递增子序列是 [7]，因此长度为 1。

解法一：动态规划（O(n²)）

1. 状态定义

定义状态 dp[i] 表示：以 nums[i] 结尾的最长递增子序列的长度。

这个状态定义很关键！注意是”以 nums[i] 结尾”，这意味着：

nums[i] 必须被包含在子序列中
子序列的最后一个元素就是 nums[i]

2. 状态转移方程

对于每个位置 i，我们需要考虑所有在它之前且值小于 nums[i] 的位置 j：

1	`dp[i] = max(dp[j] + 1) for all j where 0 ≤ j < i and nums[j] < nums[i]`

如果没有这样的 j，则 dp[i] = 1（只包含 nums[i] 自己）。

3. 边界条件

dp[0] = 1：第一个元素单独构成长度为1的递增子序列
实际上，dp[i] 的初始值都可以设为1（每个元素都能单独构成长度为1的子序列）

4. 代码实现

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int n = nums.length;
    int[] dp = new int[n];
    
    // 初始化：每个元素单独构成长度为1的子序列
    Arrays.fill(dp, 1);
    
    // 填充DP数组
    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);
            }
        }
    }
    
    // 找到所有dp[i]中的最大值
    int maxLength = 1;
    for (int length : dp) {
        maxLength = Math.max(maxLength, length);
    }
    
    return maxLength;
}

5. 算法分析

时间复杂度：O(n²) - 双重循环
空间复杂度：O(n) - dp数组
优点：思路清晰，易于理解和实现
缺点：对于大数据量效率不高

解法二：动态规划 + 二分查找（O(nlogn)）

1. 优化思路

O(n²)解法的瓶颈在于：对于每个位置，我们需要遍历前面所有位置来找到可以接在后面的最优位置。

关键观察：如果我们维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小尾部元素，那么：

tails 数组本身也是递增的
我们可以用二分查找来快速找到插入位置

2. 算法思想

维护数组 tails：

tails[i] = 长度为 i+1 的所有递增子序列中，尾部元素的最小值
遍历原数组，对于每个元素 num：
- 如果 num 大于 tails 中所有元素，直接追加到末尾
- 否则，用二分查找找到第一个大于等于 num 的位置，并替换它

3. 为什么这样做是正确的？

核心思想：我们希望递增子序列的尾部元素尽可能小，这样后续更容易接上新的元素。

例如，对于数组 [1, 3, 2, 4]：

处理到元素3时：tails = [1, 3]
处理到元素2时：发现2可以替换3，得到 tails = [1, 2]
为什么要替换？因为尾部为2的长度为2的子序列，比尾部为3的更有潜力

4. 代码实现（O(nlogn)解法）

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    List<Integer> tails = new ArrayList<>();
    
    for (int num : nums) {
        // 二分查找第一个大于等于num的位置
        int left = 0, right = tails.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails.get(mid) < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 如果找到的位置等于tails.size()，说明num比所有元素都大
        if (left == tails.size()) {
            tails.add(num);
        } else {
            // 否则替换找到位置的元素
            tails.set(left, num);
        }
    }
    
    return tails.size();
}

5. 优化版本（使用Arrays.binarySearch）

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    
    for (int num : nums) {
        // 使用Arrays.binarySearch进行二分查找
        int i = Arrays.binarySearch(tails, 0, size, num);
        
        // 如果没找到，binarySearch返回插入位置的负值
        if (i < 0) {
            i = -(i + 1);
        }
        
        tails[i] = num;
        if (i == size) {
            size++;
        }
    }
    
    return size;
}

6. 算法分析

时间复杂度：O(nlogn) - n次遍历，每次二分查找O(logn)
空间复杂度：O(n) - tails数组
优点：效率高，适合大数据量
注意：tails数组不是实际的最长递增子序列，只是用于计算长度

进阶：构造实际的最长递增子序列

上面的解法只能求出长度，如果要构造出实际的最长递增子序列，需要额外记录路径信息。

基于DP的构造方法

public List<Integer> findLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return new ArrayList<>();
    }
    
    int n = nums.length;
    int[] dp = new int[n];
    int[] prev = new int[n]; // 记录前驱节点
    Arrays.fill(dp, 1);
    Arrays.fill(prev, -1);
    
    int maxLength = 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] > maxLength) {
            maxLength = dp[i];
            maxIndex = i;
        }
    }
    
    // 构造结果
    List<Integer> result = new ArrayList<>();
    int current = maxIndex;
    while (current != -1) {
        result.add(nums[current]);
        current = prev[current];
    }
    
    Collections.reverse(result);
    return result;
}

算法选择建议

何时使用O(n²)解法？

数据量较小（n < 1000）
需要记录完整的状态转移路径
对空间复杂度有严格要求

何时使用O(nlogn)解法？

数据量较大（n > 1000）
只需要求长度，不需要构造实际序列
对时间复杂度有严格要求

总结

最长递增子序列问题是动态规划的经典问题，它展现了算法优化的精妙思想：

状态定义的艺术：选择合适的状态定义是解决DP问题的关键
优化的思路：从暴力搜索到动态规划，再到贪心+二分查找
算法工程化：不同场景下选择不同的算法实现

通过这个问题，我们不仅学会了解决具体问题的方法，更重要的是理解了算法优化的思维过程。