LeetCode 718. Maximum Length of Repeated Subarray

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/10/31/LeetCode-718-Maximum-Length-of-Repeated-Subarray/

访问原文「LeetCode 718. Maximum Length of Repeated Subarray」

题目要求

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].

Note:

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

题意解析

给两个个数组，返回两个数组中显示的子数组的最大长度。

解法分析

这个题目用传统的表格动态规划就可以，不再详细说明，请看代码。

解题代码

public int findLength(int[] A, int[] B) {
   if(A.length <= 0 || B.length <=0){
       return 0;
   }
   int maxLength = Integer.MIN_VALUE;
   int[][] map = new int[A.length][B.length];
   for(int i = 0; i < A.length; i++){
       map[i][0] = A[i] == B[0] ? 1 : 0;
       if( map[i][0] > maxLength){
           maxLength = map[i][0];
       }
   }
   for(int i = 0; i < B.length; i++){
       map[0][i] = A[0] == B[i] ? 1 : 0;
       if(map[0][i] > maxLength){
           maxLength = map[0][i];
       }
   }

   for(int i = 1; i < A.length; i++){
       for(int j = 1; j < B.length; j++){
           if(A[i] == B[j]){
               map[i][j] = map[i-1][j-1] + 1;
               if(map[i][j] > maxLength){
                   maxLength = map[i][j];
               }
           }
       }
   }
   return maxLength;
}