【Java算法】最长递增子序列，动态规划入门必学！✨

在这里插入图片描述

前言

亲爱的同学们，大家好呀！👋 今天我要和大家分享一个超级经典的算法问题——最长递增子序列（Longest Increasing Subsequence，简称LIS）。这个问题不仅是算法面试的常客，更是动态规划思想的绝佳入门案例！🌟

你是否曾经思考过，在一个看似杂乱无章的数字序列中，如何找出最长的递增部分？比如在序列 [10, 9, 2, 5, 3, 7, 101, 18] 中，最长的递增子序列是 [2, 3, 7, 18] 或 [2, 5, 7, 18]，长度为4。这个看似简单的问题，背后蕴含着丰富的算法思想！💡

今天，我将带领大家一步步揭开最长递增子序列问题的神秘面纱，从问题分析到代码实现，再到算法优化，让你彻底掌握这个经典算法！准备好开启这段算法之旅了吗？Let’s go! 🚀

知识点说明

1. 什么是最长递增子序列？🤔

最长递增子序列（LIS）是指在一个给定的数字序列中，找到一个子序列，使得这个子序列中的数字是单调递增的，且这个子序列的长度尽可能大。

需要注意的是，子序列不要求连续，只要保持原序列中的相对顺序即可。例如，序列 [3, 1, 4, 1, 5, 9] 的一个子序列可以是 [3, 4, 5, 9]。

2. 解决LIS问题的方法 🛠️

解决最长递增子序列问题主要有以下几种方法：

1. 暴力法：枚举所有可能的子序列，检查是否递增，找出最长的。时间复杂度为O(2^n)，不适用于大规模数据。
2. 动态规划法：利用动态规划思想，构建dp数组，其中dp[i]表示以第i个元素结尾的最长递增子序列的长度。时间复杂度为O(n²)。
3. 贪心 + 二分查找：维护一个递增子序列，通过二分查找优化更新过程。时间复杂度为O(nlogn)。

今天我们主要讲解动态规划方法，因为它既直观又能很好地体现动态规划的思想。

3. 动态规划的核心思想 💭

动态规划的核心在于将复杂问题分解为简单子问题，并存储子问题的解以避免重复计算。对于LIS问题：

• 状态定义：dp[i]表示以第i个元素结尾的最长递增子序列的长度。
• 状态转移方程：dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i]
• 初始状态：dp[i] = 1 for all i (每个元素自身就是一个长度为1的递增子序列)
• 最终结果：max(dp[i]) for all i

重难点说明

1. 理解子序列与子串的区别 🔍

很多同学容易混淆子序列和子串的概念：

• 子串：必须是原字符串中连续的一部分。
• 子序列：可以由原序列中不连续的元素组成，但必须保持原序列中的相对顺序。

例如，对于序列 [1, 2, 3, 4]：

• [2, 3] 既是子序列也是子串
• [1, 3] 是子序列但不是子串

在LIS问题中，我们寻找的是子序列，不要求元素连续。

2. 动态规划状态转移的理解 ⚡

状态转移是动态规划中最核心的部分。对于LIS问题，状态转移方程是：

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

这个方程的含义是：对于位置i，我们需要找到所有满足j < i且nums[j] < nums[i]的位置j，取其中dp[j]最大的值，然后加1。

为什么要这样做呢？因为如果nums[j] < nums[i]，那么我们可以将nums[i]接在以nums[j]结尾的递增子序列后面，形成一个更长的递增子序列。

3. 贪心 + 二分查找的优化思路 🚀

虽然本文主要讲解动态规划方法，但了解更优的算法也很重要。贪心 + 二分查找的核心思想是：

1. 维护一个数组tails，其中tails[i]表示长度为i+1的递增子序列的末尾元素的最小值。
2. 对于每个元素，通过二分查找找到它在tails数组中的位置，并更新tails数组。

这种方法的时间复杂度为O(nlogn)，比动态规划的O(n²)更优，适用于大规模数据。

核心代码说明

下面我们来看看最长递增子序列问题的Java实现代码：

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

public class LongestIncreasingSubsequence {
    
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        // dp[i]表示以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[n];
        // 初始化：每个元素自身就是一个长度为1的递增子序列
        Arrays.fill(dp, 1);
        
        int maxLength = 1;
        
        // 动态规划过程
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 如果当前元素大于之前的元素，可以形成更长的递增子序列
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新最长递增子序列的长度
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
}

方法二：贪心 + 二分查找（O(nlogn)）

public class LongestIncreasingSubsequence {
    
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        // tails[i]表示长度为i+1的递增子序列的末尾元素的最小值
        int[] tails = new int[n];
        int len = 0;
        
        for (int num : nums) {
            // 二分查找num在tails数组中的位置
            int left = 0, right = len;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            // 更新tails数组
            tails[left] = num;
            // 如果是在末尾添加新元素，长度加1
            if (left == len) {
                len++;
            }
        }
        
        return len;
    }
}

代码执行过程可视化 🎬

让我们通过一个例子来可视化动态规划的执行过程。假设输入数组为 [10, 9, 2, 5, 3, 7, 101, 18]：

1. 初始化dp数组：[1, 1, 1, 1, 1, 1, 1, 1]
2. i=1, nums[1]=9：
   • j=0, nums[0]=10 > nums[1]=9，不满足条件
   • dp[1]仍为1
3. i=2, nums[2]=2：
   • j=0, nums[0]=10 > nums[2]=2，不满足条件
   • j=1, nums[1]=9 > nums[2]=2，不满足条件
   • dp[2]仍为1
4. i=3, nums[3]=5：
   • j=0, nums[0]=10 > nums[3]=5，不满足条件
   • j=1, nums[1]=9 > nums[3]=5，不满足条件
   • j=2, nums[2]=2 < nums[3]=5，dp[3] = max(dp[3], dp[2]+1) = max(1, 1+1) = 2
   • dp[3]=2
5. i=4, nums[4]=3：
   • j=0, nums[0]=10 > nums[4]=3，不满足条件
   • j=1, nums[1]=9 > nums[4]=3，不满足条件
   • j=2, nums[2]=2 < nums[4]=3，dp[4] = max(dp[4], dp[2]+1) = max(1, 1+1) = 2
   • j=3, nums[3]=5 > nums[4]=3，不满足条件
   • dp[4]=2
6. i=5, nums[5]=7：
   • j=0, nums[0]=10 > nums[5]=7，不满足条件
   • j=1, nums[1]=9 > nums[5]=7，不满足条件
   • j=2, nums[2]=2 < nums[5]=7，dp[5] = max(dp[5], dp[2]+1) = max(1, 1+1) = 2
   • j=3, nums[3]=5 < nums[5]=7，dp[5] = max(dp[5], dp[3]+1) = max(2, 2+1) = 3
   • j=4, nums[4]=3 < nums[5]=7，dp[5] = max(dp[5], dp[4]+1) = max(3, 2+1) = 3
   • dp[5]=3
7. i=6, nums[6]=101：
   • 对于所有j < 6，nums[j] < nums[6]=101，dp[6] = max(dp[j]+1) = 4
   • dp[6]=4
8. i=7, nums[7]=18：
   • 类似地，dp[7]=4

最终dp数组为 [1, 1, 1, 2, 2, 3, 4, 4]，最长递增子序列的长度为4。

对Java初期学习的重要意义

1. 培养算法思维 🧠

最长递增子序列问题是动态规划的经典案例，通过学习这个问题，你可以培养解决复杂问题的能力。动态规划思想在算法领域非常重要，掌握它将帮助你解决更多高级算法问题。

2. 理解时间复杂度与算法优化 ⏱️

通过比较动态规划（O(n²)）和贪心+二分查找（O(nlogn)）两种方法，你可以深入理解算法优化的重要性。在处理大规模数据时，算法的时间复杂度往往是决定性因素。

3. 提升编程实现能力 💻

实现LIS算法需要熟练运用数组操作、循环嵌套、条件判断等基本编程技能。通过编写这些代码，你可以提升自己的编程实现能力。

4. 学习问题抽象与建模 🔄

将实际问题抽象为最长递增子序列问题是一种重要的思维训练。在软件开发中，我们经常需要将复杂的业务问题抽象为可计算的模型。

5. 为高级算法打基础 🏗️

最长递增子序列问题是许多更复杂算法的基础。掌握这个问题后，你可以更容易地理解和学习其他高级算法，如最长公共子序列、编辑距离等。

总结

亲爱的同学们，今天我们一起学习了最长递增子序列这个经典算法问题。💯

我们了解了什么是最长递增子序列，以及解决这个问题的两种主要方法：动态规划（O(n²)）和贪心+二分查找（O(nlogn)）。我们重点讲解了动态规划的思路和实现，通过定义状态、建立状态转移方程、初始化和求解最终结果四个步骤，一步步解决了这个问题。

最长递增子序列问题虽然看起来简单，但它蕴含着丰富的算法思想。通过学习这个问题，你不仅掌握了一个经典算法，更重要的是，你学会了如何用动态规划的思想解决复杂问题。这种思想在算法领域有着广泛的应用，是你算法之路上的重要里程碑。🏆

记住，算法学习不是一蹴而就的，需要不断的练习和思考。希望你能将今天学到的知识应用到更多的问题中，不断提升自己的算法能力。

如果你对最长递增子序列还有任何疑问，欢迎在评论区留言讨论。学习是一个持续的过程，让我们一起在算法的世界中探索和成长吧！✨

记得点赞、收藏、分享哦！下期我们将继续探讨更多有趣的算法知识，敬请期待！👋