【动态规划】代码随想录算法训练营第五十二天 |300.最长递增子序列， 674. 最长连续递增序列，718. 最长重复子数组（待补充）

喜欢ヅ旅行 2024-04-23 04:37 62阅读 0赞

## 300.最长递增子序列 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组 \[0,3,1,6,2,2,7\] 的子序列。

示例 1：

*  输入：nums = \[10,9,2,5,3,7,101,18\]
 *  输出：4
 *  解释：最长递增子序列是 \[2,3,7,101\]，因此长度为 4 。

示例 2：

*  输入：nums = \[0,1,0,3,2,3\]
 *  输出：4

示例 3：

*  输入：nums = \[7,7,7,7,7,7,7\]
 *  输出：1

提示：

*  1 <= nums.length <= 2500
 *  \-10^4 <= nums\[i\] <= 104

4、视频链接：

[动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列\_哔哩哔哩\_bilibili][LeetCode_300._bilibili]

class Solution {
        public int lengthOfLIS(int[] nums) {
            int[] dp = new int[nums.length];
            int res = 0;
            Arrays.fill(dp, 1);
            for (int i = 1; i < dp.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                    res = Math.max(res, dp[i]);
                }
            }
            return res;
        }
    }

## 674. 最长连续递增序列 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums\[i\] < nums\[i + 1\] ，那么子序列 \[nums\[l\], nums\[l + 1\], ..., nums\[r - 1\], nums\[r\]\] 就是连续递增子序列。

示例 1：

*  输入：nums = \[1,3,5,4,7\]
 *  输出：3
 *  解释：最长连续递增序列是 \[1,3,5\], 长度为3。尽管 \[1,3,5,7\] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

*  输入：nums = \[2,2,2,2,2\]
 *  输出：1
 *  解释：最长连续递增序列是 \[2\], 长度为1。

提示：

*  0 <= nums.length <= 10^4
 *  \-10^9 <= nums\[i\] <= 10^9

4、视频链接：

[动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列\_哔哩哔哩\_bilibili][LeetCode_674._bilibili]

/**
         * 1.dp[i] 代表当前下标最大连续值
         * 2.递推公式 if（nums[i+1]>nums[i]） dp[i+1] = dp[i]+1
         * 3.初始化 都为1
         * 4.遍历方向，从其那往后
         * 5.结果推导 。。。。
         * @param nums
         * @return
         */
        public static int findLengthOfLCIS(int[] nums) {
            int[] dp = new int[nums.length];
            for (int i = 0; i < dp.length; i++) {
                dp[i] = 1;
            }
            int res = 1;
    	//可以注意到，這邊的 i 是從 0 開始，所以會出現和卡哥的C++ code有差異的地方，在一些地方會看到有 i + 1 的偏移。
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i + 1] > nums[i]) {
                    dp[i + 1] = dp[i] + 1;
                }
                res = res > dp[i + 1] ? res : dp[i + 1];
            }
            return res;
        }

## 718. 最长重复子数组 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

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

示例：

输入：

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

提示：

*  1 <= len(A), len(B) <= 1000
 *  0 <= A\[i\], B\[i\] < 100

4、视频链接：

[动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组\_哔哩哔哩\_bilibili][DP_ _ LeetCode_718._bilibili]

class Solution {
        public int findLength(int[] nums1, int[] nums2) {
            int result = 0;
            int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    
            for (int i = 1; i < nums1.length + 1; i++) {
                for (int j = 1; j < nums2.length + 1; j++) {
                    if (nums1[i - 1] == nums2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        result = Math.max(result, dp[i][j]);
                    }
                }
            }
            return result;
        }
    }

[. - _LeetCode]: https://leetcode.cn/problems/longest-increasing-subsequence/
[Link 1]: https://www.programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html
[LeetCode_300._bilibili]: https://www.bilibili.com/video/BV1ng411J7xP
[. - _LeetCode 1]: https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
[Link 2]: https://programmercarl.com/0674.%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E9%80%92%E5%A2%9E%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_674._bilibili]: https://www.bilibili.com/video/BV1bD4y1778v
[. - _LeetCode 2]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
[Link 3]: https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[DP_ _ LeetCode_718._bilibili]: https://www.bilibili.com/video/BV178411H7hV