代码随想录算法训练营第五十二天
代码随想录算法训练营第五十二天| 300.最长递增子序列，674. 最长连续递增序列，718. 最长重复子数组
- 300.最长递增子序列
- 674. 最长连续递增序列
- 718. 最长重复子数组
300.最长递增子序列
题目链接：最长递增子序列
这里是不用处理if nums[i] <= nums[j]:的情况的，直接默认了碰到这种情况就直接放弃，有点奇怪，但也说得通。
这样的话其实dp[i]并不是nums[:(i+1)]最长严格递增子序列的长度，而是
以nums[i]为结尾的递增子序列的长度
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:# dp[i] = nums[:(i+1)]最长严格递增子序列的长度dp = [1] * len(nums)for i in range(1,len(nums)):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i],dp[j]+1)#print(dp)return max(dp)
674. 最长连续递增序列
题目链接：最长连续递增序列
和上一题一样这里的dp[i]其实是以nums[i]为结尾的连续递增子序列的长度并不是nums[:(i+1)]里的最长连续递增子序列的长度
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:# dp[i] = nums[:(i+1)]中最长且连续递增的子序列dp = [1]*len(nums)for i in range(1,len(nums)):if nums[i] > nums[i-1]:dp[i] = dp[i-1]+1return max(dp)
718. 最长重复子数组
题目链接：最长重复子数组
| i/j | 3 | 2 | 1 | 4 | 7 |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | 1 | ||||
| 3 | 1 | 1 | |||
| 2 | 2 | ||||
| 1 | 3 |
这个题的顺序是斜着走的，只要能保证左上方是遍历过的就可以了。
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:#dp[i][j] = nums1[:i]和nums2[:j]的两个数组中公共的长度最长的子数组的长度dp = [[0]*len(nums2) for _ in range(len(nums1))]m = 0for i in range(len(nums1)):if nums1[i] == nums2[0]:dp[i][0] = 1m = 1for j in range(len(nums2)):if nums2[j] == nums1[0]:dp[0][j] = 1m = 1for i in range(1,len(nums1)):for j in range(1,len(nums2)):if nums1[i] == nums2[j]:dp[i][j] = dp[i-1][j-1]+1m = max(dp[i][j],m)#print(dp)#print(m)return m