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

子序列系列

718. 最长重复子数组

dp[i][j]看nums[i] nums[j]的公共序列

class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:dp=[[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]res=0for i in range(1,len(nums1)+1):for j in range(1,len(nums2)+1):if nums1[i-1]==nums2[j-1]:dp[i][j]=dp[i-1][j-1]+1res=max(dp[i][j],res)return res

674. 最长连续递增序列

dp[i]:以i为结尾的最大递增序列长度 这样只用判断结尾的是否是递增的 否则从头开始

用res来记录历史上最大的

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

300. 最长递增子序列 

要把0-i中每个j都遍历一下和最后一个比较 找那个最大值

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums)<=1: return len(nums)dp=[1]*len(nums)res=1for i in range(1,len(nums)):for j in range(0,i):if nums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)res=max(res,dp[i])return res