代码随想录算法训练营 day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

**代码随想录算法训练营 Day52**

### **300. 最长递增子序列**

#### 题目描述：

给定一个整数数组 `nums`，返回其中最长的递增子序列的长度。

#### 示例1：

输入：`nums = [10,9,2,5,3,7,101,18]`

输出：`4`

解释：最长递增子序列是 `[2,5,7,101]`，它的长度为 `4`。

#### 示例2：

输入：`nums = [4,10,4,3,8,9]`

输出：`3`

解释：最长递增子序列是 `[3,8,9]`，它的长度为 `3`。

#### 思路：

1. 初始化一个列表 `dp`，其中每个元素代表从第0 个数字到该数字所能组成的最长递增子序列的长度。
2. 遍历数组 `nums`，对于每个数字 `num`：
* 如果 `num` 大于前面的所有数字，则 `dp[num] = dp[num-1] +1`。
* 否则，`dp[num] = max(dp[num-1], dp[num])`。

####代码：

def lengthOfLIS(nums):
 if not nums:
 return0 dp = [1] * len(nums)
 for i in range(1, len(nums)):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i] = max(dp[i], dp[j] +1)

 return max(dp)

### **674. 最长连续递增序列**

#### 题目描述：

给定一个整数数组 `nums`，返回其中最长的连续递增子序列的长度。

#### 示例1：

输入：`nums = [0,3,7,2,5,8,4,6,9,1]`

输出：`3`

解释：最长连续递增子序列是 `[0,3,7]`，它的长度为 `3`。

#### 示例2：

输入：`nums = [4,2,4,5,3,2]`

输出：`1`

解释：最长连续递增子序列是 `[2]`，它的长度为 `1`。

#### 思路：

1. 初始化一个列表 `dp`，其中每个元素代表从第0 个数字到该数字所能组成的最长连续递增子序列的长度。
2. 遍历数组 `nums`，对于每个数字 `num`：
* 如果 `num` 大于前面的所有数字，则 `dp[num] = dp[num-1] +1`。
* 否则，`dp[num] = max(dp[num-1], dp[num])`。

####代码：

def findLengthOfLCIS(nums):
 if not nums:
 return0 dp = [1] * len(nums)
 for i in range(1, len(nums)):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i] = max(dp[i], dp[j] +1)

 return max(dp)

### **718. 最长重复子数组**

#### 题目描述：

给定两个整数数组 `nums1` 和 `nums2`，返回其中最长的重复子数组的长度。

#### 示例1：

输入：`nums1 = [1,2,3,2,1]`, `nums2 = [3,2,1,4,7]`

输出：`3`

解释：最长重复子数组是 `[1,2,3]`，它的长度为 `3`。

#### 示例2：

输入：`nums1 = [0,0,0,0]`, `nums2 = [0,0,0,0,0]`

输出：`5`

解释：最长重复子数组是 `[0,0,0,0,0]`，它的长度为 `5`。

#### 思路：

1. 初始化一个列表 `dp`，其中每个元素代表从第0 个数字到该数字所能组成的最长重复子数组的长度。
2. 遍历两个数组 `nums1` 和 `nums2`，对于每对数字 `(num1, num2)`：
* 如果 `num1 == num2` 则 `dp[num1] = dp[num2] +1`。
* 否则，`dp[num1] = max(dp[num1], dp[num2])`。

####代码：

def findLength(nums1, nums2):
 if not nums1 or not nums2:
 return0 m, n = len(nums1), len(nums2)
 dp = [[0] * (n +1) for _ in range(m +1)]
 max_length =0 for i in range(1, m +1):
 for j in range(1, n +1):
 if nums1[i -1] == nums2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 max_length = max(max_length, dp[i][j])
 return max_length

以上是对这三个问题的解答，分别是最长递增子序列、最长连续递增序列和最长重复子数组。