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

作者：繁依Fanyi0 | 2024-07-29 22:18:05

踩

系列文章目录

文章目录

系列文章目录
300.最长递增子序列
674. 最长连续递增序列
718. 最长重复子数组

300.最长递增子序列

题目链接： 300.最长递增子序列
题目内容： 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
视频讲解： 动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
确定递推公式：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
dp数组如何初始化：每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1
确定遍历顺序：需要遍历i和j，遍历i的循环在外层，遍历j的循环在内层
- dp[i] 是由0到i-1各个位置的最长递增子序列推导而来，因此遍历i是从前向后遍历；
- j是遍历0到i-1，因此从前到后，还是从后到前遍历都无所谓，只要把 0 到 i-1 的元素都遍历了就行了。
举例推导dp数组

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        dp=[1]* len(nums)
        result=1
        for 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)
            result=max(result,dp[i])
        return result
1
2
3
4
5
6
7
8
9
10
11
12

674. 最长连续递增序列

题目链接： 674. 最长连续递增序列
题目内容： 给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
视频讲解： 动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：以下标i为结尾的连续递增的子序列长度为dp[i]
确定递推公式：if (nums[i] > nums[i-1]) dp[i] = dp[i - 1] + 1
dp数组如何初始化：每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1
确定遍历顺序：从前到后遍历
举例推导dp数组

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n=len(nums)
        if n == 0:
            return 0
        result=1
        dp=[1] * n 
        dp[0]=1
        for i in range(n-1):
            if nums[i]<nums[i+1]:
                dp[i+1]=dp[i]+1
            result=max(result,dp[i+1])
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13

718. 最长重复子数组

题目链接： 718. 最长重复子数组
题目内容： 给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。
视频讲解： 动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组

子数组就是连续子序列

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
确定递推公式：当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1
dp数组如何初始化：dp[i][0] 和dp[0][j]初始化为0
确定遍历顺序：A和B先遍历哪一个都可以
举例推导dp数组

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:

        dp=[[0]* (len(nums2)+1) for _ in range (len(nums1)+1)]
        result=0
        for 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]+1
                if dp[i][j]>result:
                    result=dp[i][j]
        return result
1
2
3
4
5
6
7
8
9
10
11
12

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/900843