Skip to content

Latest commit

 

History

History
55 lines (39 loc) · 1.39 KB

718-maximum-length-of-repeated-subarray.md

File metadata and controls

55 lines (39 loc) · 1.39 KB

718. Maximum Length of Repeated Subarray - 最长重复子数组

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

示例 1:

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

说明:

  1. 1 <= len(A), len(B) <= 1000
  2. 0 <= A[i], B[i] < 100

题目标签:Array / Hash Table / Binary Search / Dynamic Programming

题目链接:LeetCode / LeetCode中国

题解

Language Runtime Memory
java 15 ms 39.6 MB
class Solution {
    public int findLength(int[] A, int[] B) {
        int[] dp = new int[B.length + 1];
        int res = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = B.length - 1; j >= 0; j--) {
                dp[j + 1] = A[i] == B[j] ? dp[j] + 1 : 0;
                res = Math.max(res, dp[j + 1]);
            }
        }     
        return res;
    }
}