class Solution:
    # time: O(log(min(m, n) * (m + n) * min(m, n)))
    # space: O(m ** 2)
    def get_max_length(self, A, B):
        
        def mutual_subarray(length):
            # generate all subarrays of A with length length
            subarrays = set(tuple(A[i: i + length]) for i in range(len(A) - length + 1))

            return any(tuple(B[j: j + length]) in subarrays for j in range(len(B) - length + 1))
        
        left, right = 0, min(len(A), len(B)) - 1

        while left <= right: # search for smallest length with no mutual subarray
            mid = (right + left) // 2

            if mutual_subarray(mid):
                left = mid + 1
            else:
                right = mid - 1
        
        return left - 1
    

    #time: O(M * N)
    #space: O(M * N)
    def get_max_length2(self, A, B):
        # rows = A, cols = B
        memo = [[0 for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]

        result = 0

        for row in range(1, len(A) + 1):
            for col in range(1, len(B) + 1):
                if A[row - 1] == B[col - 1]:
                    memo[row][col] = memo[row - 1][col - 1] + 1
                    result = max(result, memo[row][col])
        
        return result
    

    ## this is the solution for the problem if the subarrays do not need to be continuous
    ## in this case, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    def get_max_length3(self, A, B):
        dp = [[0 for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]
        
        for i in range(1, len(A) + 1):
            for j in range(1, len(B) + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[-1][-1]


solution = Solution()
A = [3, 2, 1, 8, 6, 9]
B = [7, 6, 3, 2, 1, 9]
print(solution.get_max_length3(A, B))