代码随想录算法训练营第四十三天 | 300-最长递增子序列、674-最长连续递增序列、718-最长重复子数组
LeetCode300 最长递增子序列
题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
文章讲解：https://programmercarl.com/0300.最长上升子序列.html
视频讲解：https://www.bilibili.com/video/BV1ng411J7xP/?vd_source=b989f2b109eb3b17e8178154a7de7a51
动规五部曲：
- 确定dp数组以及下标的含义
dp[i]表示i之前包括i的以nums[i]为结尾的最长严格递增子序列的长度
- 确定递推公式
i在后，j在0到i之间，如果nums[i]大于nums[j]，dp[i] = Math.max(dp[i], dp[j]+1)
- dp数组如何初始化
dp数组所有下标初始化为1，因为每个元素其本身也算作一个严格递增子序列
- 确定遍历顺序
外层for循环，i从1开始往后顺序遍历；内层for循环，j从0遍历到i
- 举例推导dp数组
class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];for(int i = 0; i < nums.length; i++){dp[i] = 1;}int result = 1;for(int i = 1; i < nums.length; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){dp[i] = Math.max(dp[i], dp[j] + 1);}}result = Math.max(result, dp[i]);}return result;}
}
LeetCode674 最长连续递增序列
题目链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
文章讲解：https://programmercarl.com/0674.最长连续递增序列.html
视频讲解：https://www.bilibili.com/video/BV1bD4y1778v/?vd_source=b989f2b109eb3b17e8178154a7de7a51
动规五部曲：
- 确定dp数组以及下标的含义
dp[i]表示i之前包括i的以nums[i]为结尾的最长连续递增子序列的长度
- 确定递推公式
如果nums[i]大于nums[i-1]，则dp[i] = dp[i-1]+1；否则，dp[i] = 1
- dp数组如何初始化
dp[0] = 1
- 确定遍历顺序
一层for循环，i从1开始往后顺序遍历
- 举例推导dp数组
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];dp[0] = 1;int result = 1;for(int i = 1; i < nums.length; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}result = Math.max(result, dp[i]);}return result;}
}
LeetCode718 最长重复子数组
题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
文章讲解：https://programmercarl.com/0718.最长重复子数组.html
视频讲解：https://www.bilibili.com/video/BV178411H7hV/?vd_source=b989f2b109eb3b17e8178154a7de7a51
动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示以i-1为结尾的nums1和以j-1为结尾的nums2，二者中公共的长度最长的子数组长度
- 确定递推公式
如果nums1[i-1] == nums[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1
- dp数组如何初始化
全都初始化为0
- 确定遍历顺序
dp[i][j]中的i是以i-1为结尾的nums1，j是以j-1为结尾的nums2，所以两层for循环都是从1开始顺序遍历到nums1.length/nums2.length
- 举例推导dp数组
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int result = 0;for(int i = 1; i <= nums1.length; i++){for(int j = 1; j <= nums2.length; 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;}
}