Day 52| 300.最长递增子序列 | 674. 最长连续递增序列 | 718. 最长重复子数组

**Day52|300. 最长递增子序列 |674. 最长连续递增序列 |718. 最长重复子数组**

今天，我们将讨论三个相关的问题：最长递增子序列（Longest Increasing Subsequence, LIS）、最长连续递增序列和最长重复子数组。这些问题都涉及到找出一个序列中最长的递增或连续递增子序列。

###1. 最长递增子序列 (LIS)

给定一个整数数组 `nums`，要求找到其中最长的递增子序列的长度。例如，如果输入 `[10,9,2,5,3,7,101,18]`，输出应该是 `4`，因为最长递增子序列是 `[2,3,7,101]`。

#### 解决方案我们可以使用动态规划来解决这个问题。首先，我们需要定义一个长度为 `n` 的数组 `dp`，其中 `dp[i]` 表示 `nums[0..i-1]` 中最长递增子序列的长度。

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

#### 时间复杂度时间复杂度为 O(n^2)，因为我们需要遍历整个数组 `nums`。

###2. 最长连续递增序列给定一个整数数组 `nums`，要求找到其中最长的连续递增子序列的长度。例如，如果输入 `[1,9,3,10,4,20,2]`，输出应该是 `5`，因为最长连续递增子序列是 `[1,3,4,5,7]`。

#### 解决方案我们可以使用动态规划来解决这个问题。首先，我们需要定义一个长度为 `n` 的数组 `dp`，其中 `dp[i]` 表示 `nums[0..i-1]` 中最长连续递增子序列的长度。

def longestContinuousIncreasingSequence(nums):
 n = len(nums)
 dp = [1] * n for i in range(1, n):
 if nums[i] > nums[i -1]:
 dp[i] = dp[i -1] +1 return max(dp)

#### 时间复杂度时间复杂度为 O(n)，因为我们只需要遍历整个数组 `nums`。

###3. 最长重复子数组给定两个整数数组 `nums1` 和 `nums2`，要求找到其中最长的重复子数组的长度。例如，如果输入 `[1,2,3]` 和 `[2,3,4]`，输出应该是 `2`，因为最长重复子数组是 `[2,3]`。

#### 解决方案我们可以使用动态规划来解决这个问题。首先，我们需要定义一个长度为 `n` 的数组 `dp`，其中 `dp[i]` 表示 `nums1[0..i-1]` 和 `nums2[0..i-1]` 中最长重复子数组的长度。

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

#### 时间复杂度时间复杂度为 O(n * m)，因为我们需要遍历整个数组 `nums1` 和 `nums2`。

以上就是今天的内容。希望你能理解这些问题和解决方案，能够应用到实际的问题中去！