LeetCode 300：最长递增子序列，从“以 i 结尾”推出序列 DP

题目要求

输入输出

• 输入：整数数组 nums
• 输出：返回 nums 的最长严格递增子序列长度
• 子序列保持原数组中的相对顺序，但不要求连续，可以跳过元素
• 如果选择的下标是 i_1 < i_2 < ... < i_k，还必须满足 nums[i_1] < nums[i_2] < ... < nums[i_k]
• 子序列非空，因此至少选择一个元素
• 约束：1 <= nums.length <= 2500，-10^4 <= nums[i] <= 10^4

示例

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：[2,5,7,101] 是一个长度为 4 的严格递增子序列；它不要求在原数组中连续。

输入：nums = [0,1,0,3,2,3]
输出：4
解释：[0,1,2,3] 的长度为 4；`[0,1,3]` 也是合法但更短的选择。

这篇只用 Python，从“每个位置结尾能形成多长”这个局部问题开始，逐步写出可运行解法。

Step 1：先问“以哪个位置结束？”

先看第一个例子：

下标：  0   1  2  3  4  5    6   7
数值： 10   9  2  5  3  7  101  18

答案 [2,5,7,101] 跳过了 9 和 3。当我们走到值为 7 的位置时，不能只问“它左边相邻的数是谁”，而要问：

在它前面，哪些更小的数可以作为合法前驱？接上之后，最长能有多长？

当前 baseline 是：知道题目要找整组数组中的最长严格递增子序列，但还没有一个状态能单独描述某个位置的结果。

这会在什么地方失效？ 如果直接枚举整组候选，容易把“子序列”误当成连续子数组，也无法复用“以 2、5 或 3 结尾的结果”来判断以 7 结尾的结果。

在当前问题上先做一个改变：把问题缩小成一个按结尾位置提问的版本。

end_at_i = 必须选 nums[i]，并且以 nums[i] 作为最后一个元素时，
           最长严格递增子序列的长度

例如，对值为 7 的下标 5：

• 2 -> 5 -> 7 合法；
• 2 -> 3 -> 7 也合法；
• 10 -> 7 不合法，因为 10 < 7 不成立；
• 7 自己至少可以构成长度为 1 的序列。

对值为 101 的下标 6，则可以继续接在 7 后面。这样，整题不再一次性询问“全局最长是多少”，而是先分别回答每个位置结尾的局部问题。

检查这个改变：回到 [10,9,2,5,3,7,101,18]，end_at_i 的问题始终要求最后一个元素就是当前位置的元素，同时保留原下标顺序；它允许跳过元素，但不允许逆序或把不递增的值接上。

现在这个版本能做到：

• 区分“子序列”和“连续子数组”；
• 明确每个位置都对应一个“必须以它结尾”的更小问题；
• 看出 7 的答案需要复用更早位置的结果。

它还缺：

• 还没有为每个位置建立可运行的状态；
• 还不知道没有合法前驱时，end_at_i 应该从什么最小值开始；
• 下一步需要把这个状态写成数组，并先处理单元素 base case。

Step 2：没有前驱时，单个元素就是长度 1

现在已经知道要分别记录每个位置的 end_at_i，先处理最简单的一种情况：当前位置前面没有任何可以接上的元素。

当前 baseline 是：Step 1 只有状态的文字定义，还没有数组来保存这些状态。

这会在什么地方失效？ 如果没有合法前驱，状态就没有起点；后面即使找到一个更小的元素，也不知道应该在什么数值上继续加一。

在上一版基础上新增 base case：任何单个元素自己就是一个长度为 1 的严格递增子序列。因此把每个位置的初始值都设为 1。为了先观察这张状态表，当前函数暂时返回数组；它还不是题目要求的最终整数答案。

def length_of_lis(nums: list[int]) -> list[int]:
    n = len(nums)
    dp = [1] * n
    return dp

这里的 dp[i] 就是 Step 1 中 end_at_i 的代码表示：

dp[i] = 必须以 nums[i] 结尾的最长严格递增子序列长度

检查这个改变：只运行初始化，观察几个没有可接前驱的情形。

assert length_of_lis([7]) == [1]
assert length_of_lis([7, 7]) == [1, 1]
assert length_of_lis([10, 9, 2]) == [1, 1, 1]

重复值 [7, 7] 仍然得到两个 1，因为严格递增要求前一个值必须小于后一个值；此处还没有执行任何跨位置连接。

现在这个版本能做到：

• 为每个位置建立一个合法的单元素起点；
• 把 end_at_i 第一次落成可运行的 dp[i] 状态；
• 在没有前驱时仍能给出正确的局部长度 1。

它还缺：

• 还没有检查更早位置是否能接到当前位置前面；
• 还没有把长度为 1 的状态扩展成长度大于 1 的序列；
• 下一步需要检查每个更早且更小的位置，再更新当前状态。

Step 3：只把更早且更小的元素接到当前序列前面

现在看值为 7 的位置。它前面既有更大的 10、9，也有更小的 2、5、3。如果只看相邻位置，或者不检查数值大小，就会把不合法的顺序接进来。

当前 baseline 是：Step 2 已经为每个位置放入 1，所以每个元素都能单独成序列；但所有 dp[i] 仍然是 1。

这会在什么地方失效？ 长度大于 1 的序列必须把当前位置接在某个更早的合法序列后面。我们还没有枚举这些候选前驱，也没有判断它们能否接上。

在上一版基础上新增一次转移：处理当前位置 i 时，逐个查看所有更早的 j。只有当 nums[j] < nums[i] 时，j 才能作为前驱；接上 nums[i] 后，长度候选是 dp[j] + 1。

def length_of_lis(nums: list[int]) -> list[int]:
    n = len(nums)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return dp

这里的 max 只是在更新“以 nums[i] 结尾”的局部状态，还不是在取整数组的最终答案。j < i 保证顺序没有倒过来，nums[j] < nums[i] 则保证是严格递增，而不是允许相等。

检查这个改变：在示例中计算 i = 5（值为 7）时，逐项检查前驱：

因此 dp[5] = 3，例如来自 2 -> 5 -> 7。再检查重复值：

assert length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) == [1, 1, 1, 2, 2, 3, 4, 4]
assert length_of_lis([7, 7, 7]) == [1, 1, 1]

现在这个版本能做到：

• 扫描每个位置之前的所有候选前驱；
• 只把更早且更小的元素接到当前元素前面；
• 计算每个位置结尾的最长长度，而不是只处理相邻元素。

它还缺：

• dp 现在保存的是每个结尾位置的局部答案；
• 最长子序列可能结束在任意位置，还不能直接返回最后一个状态；
• 下一步需要把所有 dp[i] 汇总成题目要求的一个整数。

Step 4：答案是所有结尾状态中的最大值

Step 3 已经能算出每个位置结尾的长度，但题目问的是整组数组里的最长长度。最长序列不一定以最后一个元素结束。

当前 baseline 是：函数返回完整的 dp 数组，每个位置都保存了一个正确的局部答案。

这会在什么地方失效？ 直接返回 dp[-1] 等于假设最优序列必须使用最后一个元素。例如：

nums = [1, 2, 3, 0]
dp   = [1, 2, 3, 1]

最长序列 [1,2,3] 在下标 2 结束，答案是 3；dp[-1] 却只有 1。

在上一版基础上只替换答案汇总：把临时的 return dp 换成 return max(dp)。这个 max 负责比较所有结尾位置，前面已经验证过的初始化和前驱转移保持不变。为了直接提交，再把同一段逻辑放入 LeetCode 要求的 Solution 方法；包装本身不增加新算法。

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

检查这个改变：

assert Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert Solution().lengthOfLIS([0, 1, 0, 3, 2, 3]) == 4
assert Solution().lengthOfLIS([7, 7, 7, 7, 7, 7, 7]) == 1
assert Solution().lengthOfLIS([1, 2, 3, 0]) == 3

最后一个断言专门检查“最优序列结束在中间位置”的情况，确保返回的是所有 dp[i] 的最大值，而不是数组最后一个状态。

现在这个版本能做到：

• 对每个位置计算以它结尾的最长严格递增子序列长度；
• 从所有局部状态中取出全局答案；
• 作为一份完整的 LeetCode Python 提交代码运行。

它还缺：

• 还没有用完整表格慢速复算每一次状态更新；
• 还没有证明“枚举所有更早前驱”覆盖了所有合法序列；
• 还需要核对 O(n^2) 时间、O(n) 空间和边界样例。

Step 5：慢速走一遍状态表

当前 baseline 是：Step 4 已经有一份可提交的 O(n^2) 代码，能返回标准样例的答案。

这会在什么地方失效？ 只看到代码跑通，还不能确认每个 dp[i] 的含义、前驱枚举的覆盖范围、max(dp) 的必要性，以及 O(n^2) 是否符合题目约束。

在上一版基础上只新增验证证据：不改任何状态或转移，补一张完整状态表、一个不变量证明、复杂度核对和边界检查。这里不引入新的算法。

检查这个改变：沿着 nums = [10,9,2,5,3,7,101,18] 把每个位置的状态算出来：

最终状态是：

dp = [1, 1, 1, 2, 2, 3, 4, 4]

因此 max(dp) = 4，和题目示例一致。

正确性

下面把 dp[i] 的含义写成一个不变量：

处理完下标 i 后，dp[i] 等于“必须选 nums[i] 且以它结尾”的最长严格递增子序列长度。

初始情况：每个元素单独就是长度为 1 的序列，所以 dp[i] = 1 正确。

转移情况：如果一条合法序列以 nums[i] 结尾，它要么只包含 nums[i]，要么存在最后一个前驱 j，满足 j < i 且 nums[j] < nums[i]。第二种情况的长度就是 dp[j] + 1。代码枚举了所有这样的 j，并取其中最大值，因此不会漏掉任何合法前驱，也不会接入逆序或相等的元素。

答案汇总：题目没有要求最长序列必须以最后一个位置结尾，所以所有合法结尾都可能是答案；max(dp) 正好选出其中最长的一条。

复杂度

• 时间复杂度：i 和 j 的双层循环最多检查 n(n - 1) / 2 对下标，因此是 O(n^2)。
• 额外空间复杂度：只保存长度为 n 的 dp 数组，因此是 O(n)。
• 题目约束 n <= 2500，这份序列 DP 在约束内可以直接通过。

边界与常见错误

• 单元素数组的答案是 1，base case 已经覆盖。
• 全部相等时不能连接，条件必须写成严格的 nums[j] < nums[i]，不能写 <=。
• 递减数组中每个 dp[i] 都是 1。
• 子序列不要求连续，只要下标保持递增；只比较相邻元素会漏掉合法前驱。
• dp[i] 表示“必须以 i 结尾”，不是“前 i 个元素的全局答案”；两种含义不能混用。
• 最终要返回 max(dp)，不能默认最后一个位置就是最优结尾。

现在这个版本能做到：

• 用状态表复算每一次前驱选择；
• 解释 dp[i]、严格 < 和 max(dp) 为什么正确；
• 根据题目约束判断 O(n^2) 版本的适用范围。

它还缺：

• 本教程没有推导 O(n log n) 的 tails/二分优化；
• 如果输入规模超出本题约束，需要另开一篇教程，通过新的压力重新推导优化，而不是把新算法塞进本 checkpoint。

小结

• 先把全局问题拆成每个位置结尾的局部问题：dp[i]。
• 每个位置至少有单元素序列，初值是 1。
• 只从更早且更小的前驱转移：dp[i] = max(dp[i], dp[j] + 1)。
• 最长序列可以结束在任意位置，所以答案是 max(dp)。
• 在 n <= 2500 的约束下，双层循环的 O(n^2) 序列 DP 足够使用。

参考与延伸

• LeetCode 300：Longest Increasing Subsequence
• 可以用本篇的“按结尾位置定义状态”继续练习其他序列 DP 题；更大规模输入的优化方案应另开 checkpoint 推导，避免跳过本题的状态含义。