Python solution with detailed explanation

• Maximum Length of Repeated Subarray https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/

Time O(N^2) and Space O(N) DP Solution

• dp[i][j] indicates the maximum length of repeated subarray which ends at index i-1 in A and index j-1 in B i.e. index i-1 is length i when measured from the start of the array. This gives the recurrence dp[i][j] = dp[i-1][j-1] + 1 if A[i-1] == B[j-1] else 0.
• While we can initialize a 2D matrix to compute this, we really need two vectors of dimension (N+1) since the dp[i][j] just depends on the previous row.
``````class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
M, N = len(A), len(B)
dp, temp = [0]*(N+1), [0]*(N+1)
ans = 0
for i in range(1, M+1):
for j in range(1, N+1):
dp[j] = temp[j-1] + 1 if A[i-1] == B[j-1] else 0
ans = max(ans, max(dp))
temp, dp = dp, temp
return ans
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.