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

题意解析

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

解法分析

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

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
}