7-2 最长递增子序列 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
时间: 2024-04-01 17:36:56 浏览: 32
这是一道经典的动态规划问题,可以使用动态规划算法来解决。
具体的做法是:定义一个数组 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 数组,找到其中的最大值即为最长递增子序列的长度。
以下是代码实现:
相关问题
使用python,给定一个未经排序的整数数组,找到最长且连续递增的子序列,并返回该序列的长度。
可以使用动态规划来解决该问题。我们可以维护一个数组 dp,其中 dp[i] 表示以第 i 个元素结尾的最长连续递增子序列的长度。对于每个元素 nums[i],如果 nums[i] 大于 nums[i-1],则 dp[i] = dp[i-1] + 1,否则 dp[i] = 1。最后返回 dp 数组中的最大值即可。
以下是 Python 代码实现:
```python
def findLengthOfLCIS(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1] + 1
return max(dp)
```
例如,对于输入数组 [1,3,5,4,7],该函数将返回 3,因为最长连续递增子序列为 [1,3,5]。
动态规划求一个由n个整数组成的整数序列的最长递增子序列过程
动态规划求解最长递增子序列的过程如下:
1. 定义状态:令dp[i]表示以第i个数为结尾的最长递增子序列长度。
2. 初始化状态:对于任意的1 <= i <= n,初始时dp[i]都等于1,因为任何一个数都可以看作是一个长度为1的递增子序列。
3. 状态转移:对于第i个数,它可以与前面的任何一个数组成递增子序列,我们需要找到以前面某个数j为结尾的最长递增子序列长度,然后再加上1就是以第i个数为结尾的最长递增子序列长度。因此,我们可以遍历前面的所有数j,如果第j个数小于第i个数,那么以第j个数为结尾的最长递增子序列长度加1就是以第i个数为结尾的最长递增子序列长度。即:
if(nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
4. 最终结果:遍历所有的dp[i],找到其中的最大值,即为整个序列的最长递增子序列长度。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)