今日任务：
1）300.最长递增子序列
2）674.最长连续递增序列
3）718.最长重复子数组
4）复习day20
300.最长递增子序列
题目链接：300. 最长递增子序列 - 力扣（LeetCode）
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2： 输入：nums = [0,1,0,3,2,3] 输出：4 示例 3： 输入：nums = [7,7,7,7,7,7,7] 输出：1 提示： 1 <= nums.length <= 2500 -10^4 <= nums[i] <= 104
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列哔哩哔哩bilibili
思路：
这个问题可以使用动态规划来解决。我们可以定义一个状态数组
dp，其中dp[i]表示以第 i 个元素结尾的最长递增子序列的长度。具体的动态规划转移方程如下：
- 对于
dp[i]，我们需要考虑第 i 个元素与前面的元素的关系：
- 如果 nums[i] 大于 nums[j]（0 ≤ j < i），则第 i 个元素可以接在第 j 个元素后面形成一个更长的递增子序列，此时
dp[i] = max(dp[i], dp[j] + 1)。- 否则，第 i 个元素无法接在任何元素后面形成递增子序列，此时
dp[i] = 1（表示只有第 i 个元素自己构成一个递增子序列）。最终的答案就是
dp数组中的最大值。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
# 初始化状态数组
dp = [1]*n
# 动态规划转移
for i in range(1,n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i],dp[j]+1)
# 返回dp数组中的最大值
return max(dp)674.最长连续递增序列
题目链接：674. 最长连续递增序列 - 力扣（LeetCode）
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。 示例 1： 输入nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 示例 2： 输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1。 提示： 0 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列哔哩哔哩bilibili
思路：
这一题我们可以用动态规划，也可以用贪心 算法来解决这个问题。
动态规划：
我们可以定义一个状态数组
dp，其中dp[i]表示以第i个元素结尾的最长连续递增子序列的长度。初始时，所有元素的最长连续递增子序列长度都为1。然后，我们可以从第二个元素开始遍历数组，对于每个位置
i，我们判断nums[i]是否大于nums[i-1]：
- 如果是，则
dp[i] = dp[i-1] + 1，表示以当前元素结尾的最长连续递增子序列的长度比前一个元素多1；- 如果不是，则
dp[i] = 1，表示以当前元素结尾的最长连续递增子序列的长度重新开始计算。最终，我们返回状态数组
dp中的最大值即为所求的最长连续递增子序列的长度。
class Solution:
# 动态规划
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return n
# 初始化状态数组
dp = [1] * n
# 动态规划转移
for i in range(1, n):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1] + 1
# 返回dp数组中的最大值
return max(dp)贪心算法：
我们可以遍历数组，用一个变量记录当前连续递增子序列的长度，同时维护一个变量记录最长连续递增子序列的长度。
具体步骤如下：
- 初始化当前连续递增子序列的长度
cur_len和最长连续递增子序列的长度max_len，均设为1（因为至少有一个元素构成子序列）。- 从数组的第二个元素开始遍历，判断当前元素是否比前一个元素大：
- 如果是，则当前连续递增子序列的长度加1，并更新最长连续递增子序列的长度；
- 如果不是，则当前连续递增子序列的长度重新设为1。
- 最终返回
max_len即为最长连续递增子序列的长度。
class Solution:
# 贪心算法
def findLengthOfLCIS2(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return n
cur_len = 1 # 当前连续递增子序列的长度
max_len = 1 # 最长连续递增子序列的长度
for i in range(1, n):
if nums[i] > nums[i - 1]: # 当前元素比前一个元素大
cur_len += 1
max_len = max(max_len, cur_len)
else:
cur_len = 1
return max_len感想：
针对给定一个未经排序的整数数组，找到最长且连续递增的子序列，两种方法都可以解决，但在这种情况下，贪心算法更为简单且高效。
贪心算法的优势：
- 在这个问题中，连续递增子序列的最大长度实际上就是最长连续递增子序列的长度。因此，我们只需要从头到尾遍历数组一次，记录当前递增序列的起始位置和长度即可。
- 贪心算法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。
动态规划的不足：
- 对于这个问题，使用动态规划可能会过于复杂。动态规划通常用于更复杂的问题，其中状态之间存在更复杂的依赖关系，而在这个问题中，并不需要记录每个位置的状态，只需要记录当前递增序列的起始位置和长度即可。
718.最长重复子数组
题目链接：718. 最长重复子数组 - 力扣（LeetCode）
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 示例： 输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3, 2, 1] 。 提示： 注意题目中说的子数组，其实就是连续子序列 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组哔哩哔哩bilibili
思路：
这个问题可以用动态规划来解决。我们可以使用一个二维数组
dp，其中dp[i][j]表示以A[i-1]和B[j-1]结尾的公共子数组的长度。如果A[i-1]和B[j-1]相等，那么dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# 获取数组 nums1 和 nums2 的长度
m, n = len(nums1), len(nums2)
# 初始化动态规划数组 dp
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化最大公共子数组长度为 0
max_len = 0
# 遍历数组 nums1 和 nums2
for i in range(1, m + 1):
for j in range(1, n + 1):
# 如果 nums1[i-1] 和 nums2[j-1] 相等，则更新 dp[i][j] 为前一个状态加 1
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
# 更新最大公共子数组长度
max_len = max(max_len, dp[i][j])
# 返回最大公共子数组长度
return max_len
