300. 最长递增子序列

Bin大约 2 分钟

300. 最长递增子序列

📝 题目描述

给你一个整数数组 nums，请你返回其中 最长严格递增子序列 的长度。

子序列并不要求连续，只要保持相对顺序即可。

例如：

[3,6,2,7] 是 [3,6,2,7] 的子序列
[3,6,7] 也是，因为只移除 2 即可

📌 示例

示例 1

输入：


nums = [10,9,2,5,3,7,101,18]

输出：

解释：最长递增子序列为 [2,3,7,101]。

示例 2

输入：


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

输出：

示例 3

输入：


nums = [7,7,7,7,7,7]

输出：

🚀 最优解 1：动态规划 O(n²)

这是最容易理解的经典 DP 解法。

状态定义


dp[i] = 以 nums[i] 结尾的 LIS 的长度

初始值：


每个数字都可以至少成为长度 1 的序列 → dp[i] = 1

状态转移

对每个 i，遍历它之前的所有 j：


如果 nums[i] > nums[j]
dp[i] = max(dp[i], dp[j] + 1)

最终答案为：


max(dp[i])

✅ Java 代码（与你截图一致）

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int result = solution.lengthOfLIS(nums);

        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}