718. Maximum Length of Repeated Subarray - medium
문제
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
제한사항
- 1 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100
입출력 예
1
2
3
4
5
6
7
8
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].
풀이
- DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int ans = 0;
vector<vector<int>> item(A.size()+1, vector<int>(B.size()+1, 0));
// 역순으로 부터 탐색
for (int i = A.size() - 1; i >= 0; --i) {
for (int j = B.size() - 1; j >= 0; --j) {
// 현재 index의 두 vector값이 같다면,
if (A[i] == B[j]) {
// 현재 item의 값에 각 index를 1씩 더한 index의 item + 1
// 현재 index에 1씩 더한 index의 item값은,
// 이전에 탐색한 A[i+1]와 B[j+1]이 같은지 유무임
item[i][j] = item[i+1][j+1] + 1;
ans = max(ans, item[i][j]);
}
}
}
return ans;
}
};