LC300. 最长递增子序列

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

题目解析

好的，没问题。我是 AlgoMooc 的算法老师，我们现在就来把这道题彻底讲明白，保证零基础也能听懂。

---

### 题目在说什么

题目给了你一个数组，比如 [1, 5, 2, 5, 3, 7, 2]。它想让你找出一个 “最长” 的 “递增” 的 “子序列” 的长度。

• 子序列：你可以从原数组里挑出一些数字，但必须保持它们原来的先后顺序。你可以跳着选，但不能把后面的数字选到前面去。
• 比如，从 [1, 5, 2, 5, 3, 7, 2] 里，你可以挑出 [1, 2, 3, 7]，它们在原数组中的顺序是 1（第0位）→ 2（第2位）→ 3（第4位）→ 7（第5位），顺序没变，这就是一个子序列。
• 你不能挑出 [7, 1]，因为 7 在 1 后面，你不能把它放到 1 前面去。
• 递增：你挑出来的这个子序列，里面的数字必须一个比一个大。
• [1, 2, 3, 7] 就是递增的。
• [1, 5, 5] 就不是严格递增的，因为 5 没有比 5 大。
• 最长：我们要在所有可能的递增子序列里，找到那个长度最长的。

所以，对于 [1, 5, 2, 5, 3, 7, 2] 这个例子，最长的递增子序列是 [1, 2, 3, 7] 或者 [1, 2, 5, 7]，长度是 4。题目就是要我们输出这个 4。

---

### 思路是怎么来的

这个问题，我们的大脑是怎么思考的呢？我们可以用一个 “班级排座位” 的比喻来理解。

想象一下： 你是一个班主任，要给班上的同学（数组里的数字）排一个 “递增长队”。规则是：后来的同学必须比前面所有同学都高，才能排进队伍里。你想知道，最多能排多长的队伍。

我们从头开始，一个一个同学地看：

1. 第一个同学（1号）：队伍是空的，他直接站上去。以他结尾的队伍长度是 1。 [1]

2. 第二个同学（5号）：他比1号高，所以可以站在1号后面。以他结尾的队伍长度是 2。 [1, 5]

3. 第三个同学（2号）：他比1号高，但比5号矮。

• 他能不能站在1号后面？可以！因为2 > 1。这样队伍就变成了 [1, 2]，长度是 2。
• 他能不能站在5号后面？不行，因为2 < 5。
• 所以，以他结尾的最长队伍长度是 2。

4. 第四个同学（5号，第二个5）：他比1号、2号高，也等于第一个5号（但题目要求严格递增，等于不行）。

• 站在1号后面：队伍 [1, 5]，长度 2。
• 站在2号后面：队伍 [1, 2, 5]，长度 3。
• 站在第一个5号后面：不行。
• 所以，以他结尾的最长队伍长度是 3。

你发现规律了吗？

当我们处理到第 i 个同学时，我们其实是在问：“我前面有没有比我矮的同学？如果有，我站在哪个矮同学后面，能让以我结尾的队伍最长？”

这个“以我结尾的队伍最长长度”，就是我们需要的 dp[i]。

• dp[i] 的含义就是：以第 `i` 个数字结尾的递增子序列，最长能有多长。
• 每个同学自己就是一个长度为1的队伍，所以 dp[i] 至少是 1。
• 对于第 i 个同学，我们遍历他前面的所有同学 j（从 0 到 i-1）。如果 nums[j] < nums[i]（前面的同学比我矮），那么我就可以站在他后面，组成一个长度为 dp[j] + 1 的新队伍。
• 我们从所有可能的 dp[j] + 1 中，挑一个最大的，就是 dp[i] 的值。

最后，我们看所有同学的 dp 值，最大的那个，就是整个数组能排出的最长递增队伍的长度。

---

### 代码逐步拆解

现在，我们对照着代码，一步步来看这个思路是怎么实现的。

class Solution {
    public int lengthOfLIS(int[] nums) {

        // 1. 准备一个“本子”，记录每个同学能排出的最长队伍长度
        // dp[i] 就代表以第 i 个同学结尾的最长队伍长度
        int[] dp = new int[nums.length];

        // 2. 每个同学自己一个人，就是一支长度为 1 的队伍
        // 所以先把本子上所有人的初始长度都写成 1
        Arrays.fill(dp, 1);

        // 3. 准备一个“冠军记录本”，记录目前看到的最长队伍长度
        int maxLength = 1;

        // 4. 开始从第二个同学（索引1）往后看，计算每个人的 dp 值
        // 第一个同学（索引0）的 dp 值已经是 1 了，不用算
        for(int i = 1 ; i < dp.length ; i++){

            // 5. 对于第 i 个同学，我要回头看看他前面的所有同学
            // j 从 0 跑到 i-1，就是所有在他前面的人
            for(int j = 0; j < i ;j++){
               
                // 6. 关键判断：前面的同学 j 是不是比我矮？