# 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 <= len(A), len(B) <= 1000
# 0 <= A[i], B[i] < 100
import collections


class Solution(object):
    def findLength_tle(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        res = 0

        for k1, v1 in enumerate(A):
            for k2, v2 in enumerate(B):
                if v1 == v2:
                    k = 1
                    while k1 + k < len(A) and k2 + k < len(B) and A[k1 + k] == B[k2 + k]:
                        k += 1

                    res = max(res, k)
        return res

    # brtue force , optimized
    # Time Complexity: O(M*N*\min(M, N))O(M∗N∗min(M,N)), where M, NM,N are the lengths of A, B.
    # The worst case is when all the elements are equal.
    def findLength_tle2(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        # using dict to speed up the process of finding A[i] == B[j]
        d = collections.defaultdict(list)
        for k, v in enumerate(B):
            d[v].append(k)

        for k, v in enumerate(A):
            if v in d:
                for n in d[v]:
                    t = 1
                    while k + t < len(A) and n + t < len(B) and A[k + t] == B[n + t]:
                        t += 1

                    res = max(res, t)

        return res


    def findLength(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        m, n, res = len(A), len(B), 0

        dp = [[0] * n for _ in xrange(m)]

        for i in xrange(m):
            for j in xrange(n):
                if A[i] == B[j]:
                    if i > 0 and j > 0:
                        dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j])
                        res = max(res, dp[i][j])
                    else:
                        dp[i][j] = 1
        return res

    def findLength2(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        memo = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        for i in range(len(A) - 1, -1, -1):
            for j in range(len(B) - 1, -1, -1):
                if A[i] == B[j]:
                    memo[i][j] = memo[i + 1][j + 1] + 1
        return max(max(row) for row in memo)


if __name__ == '__main__':
    print Solution().findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7])
    print Solution().findLength([3, 2, 1], [3, 2, 1, 4, 7])
    print Solution().findLength([0, 0, 0, 0, 0], [0, 0, 0, 0, 0])
    print Solution().findLength([0, 0, 0, 0, 1], [1, 0, 0, 0, 0])
    print Solution().findLength([0, 1, 1, 1, 1], [1, 0, 1, 0, 1])
    print Solution().findLength([1, 0, 0, 0, 1], [1, 0, 0, 1, 1])
