nums = [10,9,2,5,3,7,101,18],找到其中最长严格递增子序列的长度
时间: 2023-09-29 08:11:16 浏览: 41
可以使用动态规划算法来解决这个问题,时间复杂度为O(n^2)。
具体思路是,维护一个长度为n的数组dp,其中dp[i]表示以nums[i]为结尾的最长递增子序列的长度。初始时,dp数组中的每个元素都为1,因为以任何一个元素结尾的最长递增子序列至少都包含该元素本身。
然后,我们枚举数组中的每个元素i,再枚举其前面的元素j,如果nums[i]大于nums[j],那么说明可以将nums[i]接在以nums[j]结尾的递增子序列后面,从而得到一个长度更长的递增子序列。因此,我们更新dp[i]的值为dp[j]+1和dp[i]中的较大值。
最终,dp数组中的最大值即为所求的最长递增子序列的长度。
下面是Python代码实现:
```
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```
对于给定的nums = [10,9,2,5,3,7,101,18],最长严格递增子序列是[2, 3, 7, 101],长度为4。因此,调用lengthOfLIS(nums)函数,返回结果为4。
相关问题
nums = [10,9,2,5,3,7,101,18],找到其中最长严格递增子序列的长度,java代码
以下是使用动态规划的 Java 代码实现最长严格递增子序列的长度:
```
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
```
解释:
1. 定义一个数组 `dp`,其中 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列的长度。
2. 初始化每个元素的子序列长度为 1。
3. 从第 2 个元素开始遍历数组,对于每个元素 `nums[i]`,遍历它之前的元素 `nums[j]`,如果 `nums[j] < nums[i]`,则更新 `dp[i]` 为 `dp[j] + 1`,表示在 `nums[j]` 的最长递增子序列后面加上 `nums[i]` 可以得到以 `nums[i]` 结尾的更长的递增子序列。
4. 每次更新 `dp[i]` 后,都需要更新最长递增子序列的长度 `maxLen`。
5. 遍历完整个数组后,`maxLen` 就是最长递增子序列的长度。
以上是一种基本的动态规划思路,时间复杂度为 $O(n^2)$,如果采用二分查找的优化方法,时间复杂度可以降为 $O(n\log n)$。
7-2 最长递增子序列 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
这是一道经典的动态规划问题,可以使用动态规划算法来解决。
具体的做法是:定义一个数组 dp,其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始化时,将 dp 数组全部初始化为 1,因为每个元素都可以单独成为一个递增子序列。
接下来,遍历数组 nums,对于每个元素 nums[i],再遍历它前面的元素 nums[j],如果 nums[j] 小于 nums[i],则可以将 nums[i] 接到 nums[j] 的后面形成一个更长的递增子序列,此时更新 dp[i] 的值为 dp[j]+1 和 dp[i] 中的较大值。
最后,遍历 dp 数组,找到其中的最大值即为最长递增子序列的长度。
以下是代码实现: