目录

718_最长重复子数组

题目

leetcode # 718. 最长重复子数组 给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

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

分析

dp题, 和编辑距离类似, 直接给出状态定义和状态转移方程, 注意子数组默认连续,子序列默认不连续。

  1. 状态定义 f[i][j]表示A[0]到A[i]的子数组和B[0]到B[j]的子数组的公共的、长度最长的子数组的长度。
  2. 状态转移方程 如果A[i]不等于B[j] 则f[i][j] = 0; 如果A[i]等于B[j] 则f[i][j] = f[i-1][j-1]+1; 当i=0或者j=0相当于第0个子数组为空串 f = 0, f数组长度为[A.length+1][B.length+1]

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
        public static int findLength(int[] A, int[] B) {
        int[][] f = new int[A.length + 1][B.length + 1];
        for (int i = 0; i < A.length + 1; i++) {
            f[i][0] = 0;
        }
        for (int j = 0; j < B.length + 1; j++) {
            f[0][j] = 0;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                // f[i][j]需要在数组下标的基础上+1, A[0],B[0]相当于f[1][1]
                if (A[i] == B[j]) {
                    f[i + 1][j + 1] = f[i][j] + 1;
                } else {
                    f[i + 1][j + 1] = 0;
                }
                res = Math.max(res, f[i+1][j+1]);
            }
        }
        return res;
    }