leetcode 718. Maximum Length of Repeated Subarray | 718. 最长重复子数组（动态规划）

短命女 2022-10-19 04:15 154阅读 0赞

## 题目 ##

[https://leetcode.com/problems/maximum-length-of-repeated-subarray/][https_leetcode.com_problems_maximum-length-of-repeated-subarray]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### Dynamic Programming \[Accepted\] ####

参考：[官方题解][Link 1]

**Intuition and Algorithm**

Since a common subarray of `A` and `B` must start at some `A[i]` and `B[j]`, let `dp[i][j]` be the longest common prefix of `A[i:]` and `B[j:]`. Whenever `A[i] == B[j]`, we know `dp[i][j] = dp[i+1][j+1] + 1`. Also, the answer is `max(dp[i][j])` over all `i, j`.

We can perform bottom-up dynamic programming to find the answer based on this recurrence. Our loop invariant is that the answer is already calculated correctly and stored in `dp` for any larger `i, j`.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_maximum-length-of-repeated-subarray]: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/bbc94fde7b234cb6aff31f7f39d5159c.png
[Link 1]: https://leetcode.com/problems/maximum-length-of-repeated-subarray/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/5282903347664421a9239cb8c4305b70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/c7fb61ce690e41adb6fd7718fcb3927a.png