河北手机网站制作哪家好seoapp推广
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存储的就是整个数组的最长递增子序列的长度。
复杂度分析
- 时间复杂度：O(n^2)，其中 n 是数组
nums的长度。这是因为有两层循环，外层循环 n 次，内层循环在最坏情况下也是 n 次。- 空间复杂度：O(n)，需要一个大小为 n 的数组
dp来存储中间结果。
注：题目来源leetcode网站