LeetCode 300. 最长递增子序列
题目核心
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。
子序列不要求连续，但要求相对顺序一致；"严格递增"意味着相等的元素不算。
输入：nums = [10,9,2,5,3,7,101,6]
输出：4
解释：最长递增子序列是 [2,3,7,101]，长度为 4
输入：nums = [0,1,0,3,2,3]
输出：4（[0,1,2,3]）解题思考过程
第一步：暴力为什么不行
每个元素"选或不选"，枚举所有子序列是 O(2ⁿ)，直接排除。
第二步：定义状态——锚定"结尾"
子序列的麻烦在于"它从哪开始都行"。换个角度，强制规定子序列在哪里结束：
dp[i]= 以nums[i]结尾的最长递增子序列的长度。
怎么求 dp[i]？看它前面的每个位置 j < i：
- 如果
nums[j] < nums[i]，可以把nums[i]接在以j结尾的子序列后面，候选长度是dp[j] + 1。 - 所有候选里取最大；如果一个能接的都没有，那
dp[i] = 1（只含自己）。
dp[i] = max(dp[j]) + 1，其中 j < i 且 nums[j] < nums[i]
（不存在这样的 j 时 dp[i] = 1）最终答案是 max(dp[i])——最长子序列可能在任意位置结尾。
第三步：记忆化 DFS 就是 DP 的递归写法
上面的递推式直接从 i 向 j 递归展开，天然是一棵树，存在大量重复子问题。加一个 mem 数组缓存每个 i 的结果：
- 这就是"记忆化搜索"。
- 和迭代 DP 共享同一条状态转移方程，只是求解方向不同：DFS 是"自顶向下，要
dp[i]才去算它依赖的dp[j]"；迭代是"自底向上，按顺序全算一遍"。
第四步：还能更优吗？
O(n²) 对本题（n ≤ 2500）已经能过。另有经典的"贪心 + 二分"（patience sorting）做法可以做到 O(n log n)，文末给代码。
当前解法：记忆化 DFS
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
// mem[i] = 以 nums[i] 结尾的 LIS 长度，-1 表示尚未计算
let mem = new Array(nums.length).fill(-1);
let max = 0;
const dfs = (arr, i, mem) => {
// 命中缓存
if (mem[i] !== -1) {
return mem[i];
}
let res = 0;
// 在前面找所有可以接在 i 前面的位置
for (let j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
res = Math.max(res, dfs(j, mem));
}
}
// 把 nums[i] 自己接上
res++;
return (mem[i] = res);
};
// LIS 可能在任意位置结尾，逐个求并取最大
for (let i = 0; i < nums.length; i++) {
max = Math.max(max, dfs(nums, i, mem));
}
return max;
};代码逐行解释
缓存数组
let mem = new Array(nums.length).fill(-1);长度值最小是 1，所以用 -1 表示"还没算过"，不会和合法答案冲突。
递归函数
const dfs = (arr, i, mem) => {
if (mem[i] !== -1) return mem[i];
...
};dfs(i) 的语义就是递推式里的 dp[i]。先查缓存，避免重复递归——没有这一行就是指数级的暴力搜索。
枚举前驱
let res = 0;
for (let j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
res = Math.max(res, dfs(arr, j, mem));
}
}
res++;- 严格递增用
<；如果题目允许非严格（相等可接）才用<=。 - 找不到任何
j时res保持 0，res++后得到dp[i] = 1，这就是边界情况的处理，不需要单独写 if。
写回缓存并返回
return (mem[i] = res);赋值表达式的值就是 res，一行同时完成"记忆化 + 返回"。
外层取最大
for (let i = 0; i < nums.length; i++) {
max = Math.max(max, dfs(nums, i, mem));
}不能直接返回 dfs(nums.length - 1)——最后一个元素未必在最长子序列里。必须对所有结尾取最大值。
执行过程示例
以 nums = [10,9,2,5,3,7,101,6] 为例，最终 mem 的值：
i=0 (10)：无可接前缀 mem[0]=1
i=1 (9) ：10 不小于 9 mem[1]=1
i=2 (2) ：都不小于 2 mem[2]=1
i=3 (5) ：可接 i=2 (2) mem[3]=mem[2]+1=2
i=4 (3) ：可接 i=2 (2) mem[4]=2
i=5 (7) ：可接 5、3（还有 2），最大 mem[3]=2 / mem[4]=2
mem[5]=3 （[2,5,7] 或 [2,3,7]）
i=6 (101)：7<101，mem[5]=3 mem[6]=4 （[2,5,7,101]）
i=7 (6) ：可接 5、3 mem[7]=3 （[2,5,6] 或 [2,3,6]）
max = 4复杂度分析
时间复杂度：O(n²) — 每个 i 扫描它前面的所有 j，每个状态只算一次
空间复杂度：O(n) — mem 数组 + 递归栈（最深 O(n)）替代写法一：迭代 DP
把递归换成双重循环，逻辑完全等价，没有爆栈风险：
var lengthOfLIS = function (nums) {
const dp = new Array(nums.length).fill(1);
let max = 1;
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
};替代写法二：贪心 + 二分，O(n log n)
维护一个 tails 数组：tails[len] 表示长度为 len+1 的递增子序列，结尾元素最小可以是多少。
贪心直觉：同样长度的子序列，结尾越小，后面越容易继续接元素。
var lengthOfLIS = function (nums) {
const tails = [];
for (const num of nums) {
// 二分找 tails 中第一个 >= num 的位置
let left = 0;
let right = tails.length;
while (left < right) {
const mid = (left + right) >> 1;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num; // 替换；left 等于长度时等价于追加
}
return tails.length;
};注意：tails 数组不一定是真实存在的某条子序列，但它的长度一定等于 LIS 长度。
易错点
严格递增用
<：条件写成<=会把相等元素也接上，长度算大。答案要对所有结尾取 max：
dfs(n-1)只是"以最后一个元素结尾"的最优，不是全局最优。记忆化初值别用 0：
dp[i]合法值最小就是 1，用 0 当"未计算"会导致边界状态被当成缓存命中。递归深度：
n到 2500 时递归链可能很长，若执行环境栈较小有爆栈风险，工程上更推荐迭代 DP。二分版查的是"第一个 ≥ num"（下界）：找上界或找不到时不追加，都会算错。