-
Notifications
You must be signed in to change notification settings - Fork 2
/
MaxLenRepeatedSubarray.java
55 lines (50 loc) · 1.63 KB
/
MaxLenRepeatedSubarray.java
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
*
* * Copyright [2017] [Haibo(Tristan) Yan]
* *
* * Licensed under the Apache License, Version 2.0 (the "License");
* * you may not use this file except in compliance with the License.
* * You may obtain a copy of the License at
* *
* * http://www.apache.org/licenses/LICENSE-2.0
* *
* * Unless required by applicable law or agreed to in writing, software
* * distributed under the License is distributed on an "AS IS" BASIS,
* * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* * See the License for the specific language governing permissions and
* * limitations under the License.
*
*/
package com.haibo.yan.algorithm.dp;
/**
* see https://leetcode.com/problems/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].
*/
public class MaxLenRepeatedSubarray {
public int findLength(int[] A, int[] B) {
if (A == null || B == null || A.length == 0 || B.length == 0) {
return 0;
}
int max = 0;
int[][] dp = new int[A.length + 1][B.length + 1];
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= B.length; j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > max) {
max = dp[i][j];
}
}
}
}
return max;
}
}