LeetCode刷题之HOT100之最长递增子序列

2024/7/10 晴，睡眠质量良好，到实验室时间9.18。知了在窗外聒噪，似乎让我安心，静下来。做题吧

1、题目描述

在这里插入图片描述

2、算法分析

给一个整数数组，要求出里面最长严格递增子序列的长度。遇到这种问题，想到的就是DP算法，将大的问题转化成小问题，再递归。算法思路：

定义状态
首先，我们定义一个数组 dp，其中 dp[i] 表示以 nums[i]结尾的最长递增子序列的长度。这个状态定义是动态规划问题的关键，它允许我们通过已解决的小问题（即子问题）来逐步构建出原问题的解。
初始化状态
由于每个元素至少可以自成一个递增子序列，因此我们将 dp 数组的所有元素初始化为 1。特别地，dp[0] 也被初始化为1，因为数组的第一个元素本身就构成了一个长度为 1 的递增子序列。
状态转移方程
对于数组中的每个元素 nums[i]（从索引 1 开始遍历，因为索引 0 已经初始化），我们检查它之前的所有元素
nums[j]（其中 j 从 0 到 i-1）。如果 nums[i] > nums[j]，则说明我们可以将 nums[i] 加到以nums[j] 结尾的递增子序列的末尾，从而形成一个更长的递增子序列。此时，我们需要更新 dp[i] 为 dp[j] + 1 和dp[i] 之间的较大值，以确保 dp[i] 总是存储以 nums[i] 结尾的最长递增子序列的长度。

状态转移方程可以表示为：

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

记录结果在遍历过程中，我们还需要记录一个全局的最大值 maxRes，用于存储遍历到目前为止找到的最长递增子序列的长度。每次更新dp[i] 后，我们都将其与 maxRes 进行比较，并更新 maxRes 为较大值。
返回结果遍历完整个数组后，maxRes 中存储的就是整个数组的最长递增子序列的长度，我们将其作为函数的返回值。

3、代码

public int lengthOfLIS(int[] nums) {// 如果数组为空，则最长递增子序列的长度为0if(nums.length == 0){return 0;}// 创建一个dp数组来存储以每个元素为结尾的最长递增子序列的长度  // dp[i]表示以nums[i]为结尾的最长递增子序列的长度int[] dp = new int[nums.length];// 初始化dp数组，因为每个元素至少可以自成一个递增子序列dp[0] = 1;// 初始化最长递增子序列的长度为1（至少包含自身）int maxRes = 1;// 遍历数组中的每个元素（除了第一个元素，因为已经初始化）for(int i = 1; i < nums.length; i++){// 初始化dp[i]为1，因为每个元素至少可以自成一个递增子序列dp[i] = 1;// 遍历当前元素之前的所有元素for(int j = 0; j < i; j++){// 如果当前元素大于之前的某个元素，说明可以将当前元素添加到以nums[j]为结尾的递增子序列之后  // 从而形成一个更长的递增子序列  if(nums[i] > nums[j]){// 更新dp[i]为当前已找到的最长递增子序列长度+1和dp[i]中的较大值 dp[i] = Math.max(dp[i], dp[j] + 1);}}// 更新最长递增子序列的长度，取当前遍历过的所有dp[i]中的最大值maxRes = Math.max(maxRes, dp[i]);}// 返回最长递增子序列的长度return maxRes;}

4、复杂度分析

时间复杂度： $O(n^{2})$ ，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n)
的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 $O(n^{2})$ 。
空间复杂度：O(n)，需要额外使用长度为 n 的 dp 数组。