当前位置：首页 > news >正文

leetcode hot100【LeetCode 300. 最长递增子序列】java实现

news 2025/6/18 6:52:21

LeetCode 300. 最长递增子序列

题目描述

给定一个未排序的整数数组 nums，找出其中最长递增子序列的长度。

要求：

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例 1:

输入: nums = [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长递增子序列为 [2,3,7,101]，因此长度为 4。

示例 2:

输入: nums = [0,1,0,3,2,3]
输出: 4
解释: 最长递增子序列为 [0,1,2,3] 或 [0,1,3] 或 [0,3,2,3]，长度均为 4。

示例 3:

输入: nums = [7,7,7,7,7]
输出: 1
解释: 最长递增子序列为 [7]，长度为 1。

Java 实现代码

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

解题思路

边界条件处理：

如果输入数组 nums 为空，直接返回长度为 0。

初始化：

创建一个长度与 nums 相同的数组 dp，用于存储到每个位置为止的最长递增子序列的长度。
使用 Arrays.fill(dp, 1) 将 dp 数组的所有元素初始化为 1，因为每个元素自身可以看作是一个长度为 1 的递增子序列。

动态规划过程：

外层循环遍历数组 nums 的每个元素，从第二个元素开始（索引 1）。
内层循环遍历当前元素之前的所有元素（索引 0 到 i-1）。
如果当前元素 nums[i] 大于之前的某个元素 nums[j]，则说明可以通过添加 nums[i] 来扩展以 nums[j] 结尾的递增子序列。
更新 dp[i] 为 dp[j] + 1，表示以 nums[i] 结尾的递增子序列的长度。
同时，更新 maxLength 为 dp[i] 和当前 maxLength 的最大值，以记录遍历过程中找到的最长递增子序列的长度。

返回结果：

遍历完成后，maxLength 存储的就是整个数组的最长递增子序列的长度。