首页 > 其他分享 >Day 45 | 300.最长递增子序列 、674. 最长连续递增序列 、718. 最长重复子数组

Day 45 | 300.最长递增子序列 、674. 最长连续递增序列 、718. 最长重复子数组

时间:2024-07-09 23:30:59浏览次数:20  
标签:nums max 递增 len 序列 最长 dp

300.最长递增子序列

今天开始正式子序列系列,本题是比较简单的,感受感受一下子序列题目的思路。
视频讲解:https://www.bilibili.com/video/BV1ng411J7xP
https://programmercarl.com/0300.最长上升子序列.html
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        #以nums[i]为结尾的最长递增子序列
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)
        max_l = 0
        for lens in dp:
            max_l = max(lens,max_l)
        return max_l

674. 最长连续递增序列

本题相对于昨天的动态规划:300.最长递增子序列 最大的区别在于“连续”。 先尝试自己做做,感受一下区别
视频讲解:https://www.bilibili.com/video/BV1bD4y1778v
https://programmercarl.com/0674.最长连续递增序列.html
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        #以nums[i]为结尾的最长连续递增子序列
        dp = [1]*len(nums)
        for i in range(1,len(nums)):
            if nums[i]>nums[i-1]:
                dp[i]=dp[i-1]+1
        max_l = 0
        for lens in dp:
            max_l = max(max_l,lens)
        return max_l

718. 最长重复子数组

稍有难度,要使用二维dp数组了
视频讲解:https://www.bilibili.com/video/BV178411H7hV
https://programmercarl.com/0718.最长重复子数组.html

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例:

输入:

A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3, 2, 1] 。

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))]
        for j in range(len(nums2)):
            if nums2[j] == nums1[0]:
                dp[0][j] = 1
        for i in range(len(nums1)):
            if nums1[i] == nums2[0]:
                dp[i][0] = 1        
        for 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] + 1
        max_l = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                max_l = max(max_l,dp[i][j])
        return max_l

标签:nums,max,递增,len,序列,最长,dp
From: https://www.cnblogs.com/forrestr/p/18292946

相关文章