LeetCode 最长重复子数组 Maximum Length of Repeated Subarray

本文介绍了LeetCode 最长重复子数组 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] < 10

解法，这是一道经典的动态规划算法，如下：

public class MaxLengthRepeatedSubarray {
    //动态规划算法
    public static int findLength(int[] A, int[] B) {
        int aSize = A.length;
        int bSize = B.length;
        int[][] dp = new int[aSize + 1][bSize + 1];
        int result = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1 : 0;
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 2, 1};
        int[] b = new int[]{3, 2, 1, 4, 7};
        System.out.println(findLength(a, b));
    }
}

 相关推荐：

LeetCode 2 Evaluate Reverse Polish Notation

python 用list of lists表示矩阵的问题？

Atas ialah kandungan terperinci LeetCode 最长重复子数组 Maximum Length of Repeated Subarray. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!