代码随想录第43天

300.最长递增子序列

# Dynamic programming.
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if not nums: return 0dp = [1] * len(nums)for i in range(len(nums)):for j in range(i):if nums[j] < nums[i]: # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。dp[i] = max(dp[i], dp[j] + 1)return max(dp)

674. 最长连续递增序列

class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:l = 0  # 起点r = 0  # 终点maxLen = 0  # 待返回的最长长度while r < len(nums):if r == l or nums[r - 1] < nums[r]:  # 保持递增maxLen = max(maxLen, r - l + 1)  # 比较取大r += 1  # 终点前进else:  # 递增中断l = r  # 更新起点return maxLen

718. 最长重复子数组

class Solution:def findLength(self, A, B):m, n = len(A), len(B)ans = 0dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]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] + 1ans = max(ans, dp[i][j])return ans