最长递增子序列的动态规划解法

1. 概述

在本篇教程中，我们将一起探讨一个经典的动态规划问题：最长递增子序列（Longest Increasing Subsequence，简称 LIS）。

这个问题在算法面试和实际应用中都比较常见，掌握它的解法对提升算法思维和编码能力非常有帮助。

2. 问题描述

给定一个无序数组，目标是找出其中最长递增子序列的长度。这个子序列中的元素不必连续，但必须保持递增顺序。

注意：递增是严格递增（strictly increasing），即每个元素必须大于前一个。

2.1 示例

输入数组为：{-3, 10, 5, 12, 15}
可能的递增子序列包括：

• -3, 10, 12, 15
• -3, 5, 12, 15 ✅
• 10, 12, 15
• 5, 12, 15
• 12, 15

其中最长的是 -3, 5, 12, 15 和 -3, 10, 12, 15，长度均为 4。

3. 暴力解法（Naive Approach）

最直观的思路是：枚举所有子序列，然后找出其中最长的递增子序列。

实现伪代码：

algorithm NaiveLIS(array):
    // INPUT
    //    array = The input array
    // OUTPUT
    //    LIS = The longest increasing subsequence
    while true:
        Sub <- all possible subsequences of array
        maxLis <- 1
        for S in Sub:
            if isIncreasing(S):
                len <- length(S)
                maxLis <- max(maxLis, len)
        return maxLis

时间复杂度分析：

• 一个长度为 n 的数组有 2ⁿ 个子集
• 所以时间复杂度是 **O(2ⁿ)**，在 n 较大时根本不可行 ❌

4. 动态规划解法（DP Approach）

我们可以使用动态规划来优化时间复杂度。

解法思路：

1. 创建一个 dp 数组，dp[i] 表示以 arr[i] 结尾的最长递增子序列长度
2. 初始化所有 dp 值为 1（每个元素自己就是一个长度为 1 的子序列）
3. 遍历数组，对于每个元素 arr[i]，查看前面所有比它小的元素 arr[j]（j < i）
   • 如果 arr[i] > arr[j]，说明可以接在 arr[j] 后面
   • 更新 dp[i] = dp[j] + 1，前提是这个值比当前 dp[i] 大

Java 示例代码：

public static int longestIncreasingSubsequence(int[] arr) {
    int n = arr.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    return Arrays.stream(dp).max().orElse(1);
}

时间复杂度分析：

• 外层循环 O(n)
• 内层循环 O(n)
• 总体复杂度为 O(n²) ✅，相比暴力解法有了显著优化

举个例子：

输入：{ -3, 10, 5, 12, 15 }
dp 数组的变化如下：

index	arr[i]	dp[i]
0	-3	1
1	10	2
2	5	2
3	12	3
4	15	4

最终结果是 4，正确 ✅

5. 小结

• LIS 是一个经典的动态规划问题
• 暴力解法虽然直观但效率极低，不适用于 n 较大的场景
• 使用 DP 可将复杂度优化到 O(n²)，在大多数实际场景中已经足够使用
• 如果你对性能还有更高要求，还可以使用二分查找 + 贪心 + DP的方式将复杂度优化到 O(n log n)，我们留作后续文章再讲

✅ 踩坑提醒：在写 DP 状态转移逻辑时，一定要注意边界条件和比较逻辑，否则很容易出现越界或死循环等问题。建议写完后用小数据集手动跑一遍逻辑。