LeetCode 300. 最长递增子序列

◎

本节目标

枚举每个位置可接上的更早更小元素，得到以该位置结尾的最长严格递增序列。

这是序列与字符串动态规划中位置状态的基础母题。

题意与约束

求数组中严格递增子序列的最大长度；子序列可以跳过元素，不要求连续。

第一反应与重复子问题

若某个更早元素更小，就能接到当前位置之前；每个位置的最优长度会成为后续位置的前驱。

状态定义与转移推导

令 dp[i] 为以 nums[i] 结尾的最长递增子序列长度，初值为一。枚举 j<i，若 nums[j]<nums[i]，更新 dp[i]=max(dp[i],dp[j]+1)。

正确性依据

任何以 i 结尾的严格递增子序列去掉最后元素后，必以某个更小的 j 结尾；枚举全部 j 即穷尽前驱。

样例执行过程

对 [10,9,2,5,3,7,101,18]，位置 101 可接上长度为三的前驱，得到答案 4。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        vector<int> length(nums.size(), 1);
        int answer = 1;
        for (int right = 0; right < static_cast<int>(nums.size()); right++) {
            for (int left = 0; left < right; left++) {
                if (nums[left] < nums[right]) {
                    length[right] = max(length[right], length[left] + 1);
                }
            }
            answer = max(answer, length[right]);
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        if not nums:
            return 0
        lengths = [1] * len(nums)
        answer = 1
        for right in range(len(nums)):
            for left in range(right):
                if nums[left] < nums[right]:
                    lengths[right] = max(lengths[right], lengths[left] + 1)
            answer = max(answer, lengths[right])
        return answer

复杂度分析

双层枚举时间 O(n²)，位置状态数组空间 O(n)。

边界与易错点

• 相等元素不能延长严格递增序列。
• 本题使用位置 DP，不把二分优化混入基础模型。

模式迁移

最长递减、最大整除子集等题同样先定义“以当前位置结尾”的最优状态，再调整可接条件。