AlgoPressAppearance
0718-最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
提示：
- 1 <= nums1.length, nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 100
思路
csharp
public class Solution {
public int FindLength(int[] nums1, int[] nums2) {
// 动态规划，定义 dp[i,j] 表示 nums1 前i个数字和 nums2 前j个数字公共的长度最长的子数组
// 状态转移 dp[i,j] = nums1[i-1] == nums2[j-1] ? dp[i-1,j-1] + 1 : 0
// 注意： 题目的意思是子数组需要连续的
int m = nums1.Length;
int n = nums2.Length;
int[,] dp= new int[m+1,n+1];
int max = 0;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(nums1[i-1] == nums2[j-1]){
dp[i,j] = dp[i-1,j-1] + 1;
}
else{
// dp[i,j] = Math.Max(dp[i-1,j],dp[i,j-1]); //如果可以不连续，则取前面的最大值
dp[i,j] = 0; //因为题目隐含要求是连续的，所以不相等的时候，从此处就需要置零
}
max = Math.Max(max,dp[i,j]);
}
}
return max;
}
}
复习:20220515
csharp
public class Solution {
public int FindLength(int[] nums1, int[] nums2) {
int m = nums1.Length;
int n = nums2.Length;
int[,] dp = new int[m+1,n+1];
int max = 0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(nums1[i-1] == nums2[j-1]){
dp[i,j] = dp[i-1,j-1]+1;
}
else{
dp[i,j] = 0;
}
max = Math.Max(max,dp[i,j]);
}
}
return max;
}
}