动态规划中等1 种解法

#300最长递增子序列

返回整数数组中严格递增子序列的最大长度，子序列不要求连续。

#数组#动态规划#二分查找

解题主线

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

枚举 i 之前的 j；只要 nums[j] < nums[i]，就能把 nums[i] 接到以 j 结尾的序列后。

该一维模型也是第 354 题二维信封嵌套在排序降维后的核心。

解法 1：以当前位置结尾的动态规划

将所有状态初始化为 1，对每个位置枚举更早且值更小的结尾，取可转移长度的最大值。

时间复杂度

O(n²)

空间复杂度

O(n)

300. 最长递增子序列 · 以当前位置结尾的动态规划

java

import java.util.Arrays;

final class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int maximumLength = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maximumLength = Math.max(maximumLength, dp[i]);
        }
        return maximumLength;
    }
}

将所有状态初始化为 1，对每个位置枚举更早且值更小的结尾，取可转移长度的最大值。

边界与易错点

题目要求严格递增，相等元素不能接在序列后。
子序列可以跳过元素，不要误用连续窗口。
旧类名写成 lengthOfLTS，题目和方法实际都是 LIS。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q300_lengthOfLTS.java