Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].
Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].
Constraints:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
动态规划：
这题和0712非常类型，对题目最最小的添加操作就可以找到和子问题的关系。
比如存在nums1 和 nums2两个数组，针对nums1加入x元素在尾部，此时新问题和子问题的关系：
如果x不用，则新问题的解等于nums1和nums2的解
如果x使用，则
1. 在nums2[:len(nums2)-1] 前使用。变成了nums1+x和nums2[:len(nums2)-1]的解。
2. 在nums2[len(nums2)-1]使用。如果nums2[len(nums2)-1]和x相等，则计算产生新的maxLength。否则不用计算。
假设dp[i][j]存储的是nums1[:i+1](包括i)和nums2[:j+1](包括j)问题的解
则dp[i][j] = max(dp[i-1][j], dp[i][j-1], newRes)
newRes即为2的情况。
难点:需要一个新的辅助二维数组cacahe存储使用nums1[i]和nums2[j]是的maxLength
比如针对 nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
cache[3][1] = 1 表示针对子问题[1,2,3]和[3], 使用了第一个数组3和第二个数组3能得到的maxLength
cache是用来解决全部元素相同的情况。
func findLength(nums1 []int, nums2 []int) int {
dp := make([]int, len(nums1)+1)
cache := make([][]int, len(nums2)+1)
for i := 0; i < len(nums2)+1; i++ {
cache[i] = make([]int, len(nums1)+1)
}
for i := 1; i <= len(nums2); i++ {
for j := 1; j <= len(nums1); j++ {
newRes := 0
if nums2[i-1] == nums1[j-1] {
cache[i][j] = cache[i-1][j-1] + 1
newRes = cache[i][j]
}
dp[j] = max(dp[j], max(dp[j-1], newRes))
}
//fmt.Printf("%+v\n", dp)
}
return dp[len(nums1)]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}