[리트코드] 718. Maximum Length of Repeated Subarray

문제

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

풀이

두 배열의 가장 긴 공통 부분 배열 길이를 찾아 출력하는 문제이다. 옛날에 학교에서 문자열 일치 알고리즘 방식을 이용해서 풀었다.
2차원 배열을 떠올려보자. 행, 열 에는 문제에서 주어진 nums1, nums2 배열 값들이 들어있다. 이중 for문을 돌면서 두 숫자가 일치하면? 이전에 구했던 dp[i-1][j-1]값에 +1 해줘서 이어지는 길이를 구할수 있다.

코드

class Solution {
    public int findLength(int[] A, int[] B) {
        int ans = 0;
        int[][] memo = new int[A.length + 1][B.length + 1];
        for (int i = 1; i < A.length + 1 ; i++) {
            for (int j = 1 ; j< B.length + 1 ; j ++) {
                if (A[i-1] == B[j-1]) {
                    memo[i][j] = memo[i-1][j-1] + 1;
                    if (ans < memo[i][j]) ans = memo[i][j];
                }
            }
        }
        return ans;
    }
}