300. 最长递增子序列
中等
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
📝 核心笔记：最长递增子序列 (LIS – DFS Version)
1. 核心思想 (一句话总结)
“接龙游戏：每一个数字都回头看，找出比自己小的‘前驱’中尾巴最长的那一个，接在它后面。”
- 状态定义：dfs(i) 表示以 nums[i]结尾 的最长递增子序列的长度。
- 转移逻辑：遍历 j < i。如果 nums[j] < nums[i]，说明 i 可以接在 j 后面。我们想要 max(dfs(j))。
- 结果：答案不仅仅是 dfs(n-1)，而是所有位置 dfs(0…n-1) 中的最大值。
2. 算法流程 (DFS + 记忆化)
-
- LIS 可能结束在数组的任意位置（不一定在最后一个数）。
- 因此主函数必须遍历 i 从 0 到 n-1，计算每个位置的 dfs(i)，并维护一个全局最大值 ans。
-
- dfs(i)：计算以 i 结尾的 LIS 长度。
- 查表：memo[i] > 0 则直接返回。
-
- 遍历所有 j < i。
- 接龙条件：只有 nums[j] < nums[i] 时，nums[i] 才能接在 nums[j] 后面。
- 更新：res = Math.max(res, dfs(j))。
-
- res++。这一步非常关键，因为哪怕前面没有比我小的，我自身也算长度 1。
- 存入 memo[i] 并返回。
🔍 代码回忆清单
// 题目：LC 300. Longest Increasing Subsequence
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
// memo[i]: 以 nums[i] 结尾的最长子序列长度
// 初始化为 0，因为长度至少是 1，0 可以代表未计算
int[] memo = new int[n];
int ans = 0;
// 1. 必须遍历每一个位置作为"结尾"的可能性
// 易错点：不能只 return dfs(n-1)
for (int i = 0; i < n; i++) {
ans = Math.max(ans, dfs(i, nums, memo));
}
return ans;
}
private int dfs(int i, int[] nums, int[] memo) {
// 2. 记忆化检查
if (memo[i] > 0) {
return memo[i];
}
int res = 0; // 记录前面能找到的最长链
// 3. 回头看：遍历所有在 i 之前的元素 j
for (int j = 0; j < i; j++) {
// 4. 接龙条件：必须比我小
if (nums[j] < nums[i]) {
res = Math.max(res, dfs(j, nums, memo));
}
}
// 5. 加上自己：无论前面有没有人，我自己算 1 个长度
res++;
return memo[i] = res;
}
}
⚡ 快速复习 CheckList (易错点)
- [ ] 为什么主函数要循环 dfs(i)？
-
- 这是 LIS 问题的特性。最长子序列不一定包含最后一个元素。例如 [1, 2, 3, 0]，最长的是 [1,2,3] 结尾在 index 2，而不是 index 3。
- [ ] res++ 的位置？
-
- 一定要在循环结束后加。
- 如果 j 循环一次都没进去（没有比 i 小的），res 是 0，res++ 后变成 1（它自己单独成列）。这是正确的 Base Case。
- [ ] 时间复杂度？
-
- 。状态有 $N$ 个，每个状态内部需要循环 $i$ 次（平均 ）。
- 虽然有 的贪心+二分法，但 DFS/DP 写法是理解状态转移的基础。
🖼️ 数字演练
nums = [1, 4, 3]
-
- 调用 dfs(0)。
- j 循环 (空)：前面没人。
- res = 0 -> res++ -> 1。
- memo[0] = 1。更新 ans = 1。
-
- 调用 dfs(1)。
- j=0 (值 1)：1 < 4 (满足)。调用 dfs(0) 得到 1。res 更新为 1。
- res++ -> 2。
- memo[1] = 2。更新 ans = 2。
-
- 调用 dfs(2)。
- j=0 (值 1)：1 < 3 (满足)。调用 dfs(0) 得到 1。res 更新为 1。
- j=1 (值 4)：4 > 3 (不满足)。跳过。
- res++ -> 2。
- memo[2] = 2。ans 保持 2。
📝 核心笔记：最长递增子序列 (LIS – DP Version) 递推
1. 核心思想 (一句话总结)
“接龙比赛：轮到我（第 i 个）接龙时，我回头看所有比我小的队友（j），挑一个最长的队伍接在后面。”
- 状态定义：f[i] 表示以 nums[i]结尾 的最长递增子序列的长度。
- 状态转移：f[i] = max(f[j]) + 1，其中 0 <= j < i 且 nums[j] < nums[i]。
2. 算法流程 (双重循环)
-
- f 数组初始化。Java 中默认是 0，我们可以在循环内做 ++f[i] 来处理 Base Case（即自己本身长度为 1）。
-
- 遍历每个位置 i，把它当作子序列的 尾部。
-
- 回头扫描所有 j < i。
- 接龙判定：如果 nums[j] < nums[i]，说明 i 可以接在 j 后面。
- 更新：f[i] = Math.max(f[i], f[j])。这里 f[i] 暂时存的是“在 i 之前能找到的最长长度”。
-
- 内层循环结束后，f[i] 加上自己的 1：++f[i]。
- 同时更新全局最大值 ans。
🔍 代码回忆清单
// 题目：LC 300. Longest Increasing Subsequence
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int ans = 0;
// f[i] 表示以 nums[i] 结尾的最长递增子序列长度
int[] f = new int[n];
// 1. 外层循环：计算每个位置 i 的 f[i]
for (int i = 0; i < n; i++) {
// 2. 内层循环：在 i 之前找可以接龙的 j
for (int j = 0; j < i; j++) {
// 3. 核心判断：只有比我小，我才能接在他后面
if (nums[j] < nums[i]) {
// 维护一个最大值：谁的队伍长，我就接谁
f[i] = Math.max(f[i], f[j]);
}
}
// 4. 加上自己：把自己接上去，长度 +1
// 写法技巧：++f[i] 先加再用，既更新了 f[i]，又参与了 ans 的比较
ans = Math.max(ans, ++f[i]);
}
return ans;
}
}
⚡ 快速复习 CheckList (易错点)
- [ ] 为什么内层循环结束后要 ++f[i]？
-
- 在内层循环中，f[i] 收集的是“前驱的最大长度”。
- 比如 [1, 5]，算 5 时，找到 1 的长度是 1，此时 f[1] 暂存为 1。
- 只有加上 5 自己，长度才变成 2。这也处理了 j 循环没命中的情况（f[i] 初始 0，加完变 1）。
- [ ] 能不能初始化 f 全为 1？
-
- 可以。这也是常见写法：Arrays.fill(f, 1)。
- 这样内层循环就写成 f[i] = Math.max(f[i], f[j] + 1)。
- 您的写法（默认 0，最后 ++）更省一步初始化操作，效率微高一点点。
- [ ] 时间复杂度？
-
- 。标准的双重循环。
- 进阶：如果面试官问“能优化到 吗？”，那是贪心 + 二分查找的解法（维护一个 tails 数组），与本题 DP 逻辑不同。
🖼️ 数字演练
nums = [10, 9, 2, 5, 3, 7]
-
- j=2 (2 < 5): f[3] = max(0, f[2]=1) = 1.
- End: ++f[3] -> 2 ([2, 5]). ans=2.
-
- j=2 (2 < 3): f[4] = max(0, f[2]=1) = 1.
- End: ++f[4] -> 2 ([2, 3]). ans=2.
-
- j=2 (2 < 7): f[5] = 1.
- j=3 (5 < 7): f[5] = max(1, f[3]=2) = 2.
- j=4 (3 < 7): f[5] = max(2, f[4]=2) = 2.
- End: ++f[5] -> 3 ([2, 5, 7] or [2, 3, 7]). ans=3.
