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

300.最长递增子序列

力扣题目链接(opens new window)

给你一个整数数组 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

最长递增子序列（Longest Increasing Subsequence，简称 LIS）问题的核心思路是维护一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

---

思路

1. 初始化：初始化 dp 数组，每个元素的初始值为 1，因为每个元素自身至少可以构成一个长度为 1 的递增子序列。

2. 状态转移：遍历数组，对于每个 nums[i]，再遍历其之前的所有元素 nums[j]（其中 j < i）。如果 nums[j] < nums[i]，表示 nums[i] 可以接在 nums[j] 形成的递增子序列之后，此时更新 dp[i] 为 max(dp[i], dp[j] + 1)。

3. 求解：最终答案是 dp 数组中的最大值，即所有以 nums[i] 结尾的最长递增子序列的最大长度。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
 
        n = len(nums)
        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)
 
        return max(dp)

674. 最长连续递增序列

力扣题目链接(opens new window)

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 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

思路

1. 初始化：定义两个变量，一个用来存储当前连续递增子序列的长度（curr_length），另一个用来存储到目前为止找到的最长连续递增子序列的长度（max_length）。初始时，两者都设为 1（因为至少每个元素可以构成长度为 1 的子序列）。

2. 遍历数组：从第二个元素开始遍历数组。对于每个元素，如果它比前一个元素大，那么 curr_length 加一，表示当前连续递增序列被延长了。如果当前元素不大于前一个元素，说明连续递增序列被打断了，此时应该重置 curr_length 为 1。

3. 更新最大长度：在遍历过程中，每次 curr_length 变化时，都要检查并更新 max_length。

4. 结果：遍历结束后，max_length 就是最长连续递增子序列的长度。

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        max_length = 1
        curr_length = 1
 
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                curr_length += 1
                max_length = max(max_length, curr_length)
            else:
                curr_length = 1
 
        return max_length

718. 最长重复子数组

力扣题目链接(opens new window)

给两个整数数组 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

  ---

  思路

• 定义状态：创建一个二维数组 dp，其中 dp[i][j] 表示数组 A 中以 i-1 结尾和数组 B 中以 j-1 结尾的最长公共子数组的长度。注意这里的 i 和 j 是从 1 开始的，以便处理边界情况。

• 状态转移：遍历数组 A 和 B，对于每一对 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。

• 记录最大值：在填充 dp 的过程中，记录 dp[i][j] 的最大值，这将是最长公共子数组的长度。

• 返回结果：遍历完成后，返回记录的最大值。

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        m, n = len(A), len(B)
        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 A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    max_length = max(max_length, dp[i][j])
                else:
                    dp[i][j] = 0
 
        return max_length