• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
const int m = nums1.size();
const int n = nums2.size();
int ans = 0;
// dp[i][j] := max length of nums1[i:] and nums2[j:]
vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int i = m - 1; i >= 0; --i)
for (int j = n - 1; j >= 0; --j)
if (nums1[i] == nums2[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
ans = max(ans, dp[i][j]);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int findLength(int[] nums1, int[] nums2) {
final int m = nums1.length;
final int n = nums2.length;
int ans = 0;
// dp[i][j] := max length of nums1[i:] and nums2[j:]
int[][] dp = new int[m + 1][n + 1];

for (int i = m - 1; i >= 0; --i)
for (int j = n - 1; j >= 0; --j)
if (nums1[i] == nums2[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
ans = Math.max(ans, dp[i][j]);
}

return ans;
}
}
``````

## Python

``````class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m = len(nums1)
n = len(nums2)
ans = 0
# dp[i][j] := max length of nums1[i:] and nums2[j:]
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in reversed(range(m)):
for j in reversed(range(n)):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i + 1][j + 1] + 1
ans = max(ans, dp[i][j])

return ans
``````

• Time:O(mn)
• Space:O(n)

## C++

``````class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
const int m = nums1.size();
const int n = nums2.size();
int ans = 0;
vector<int> dp(n + 1);

for (int i = m - 1; i >= 0; --i)
for (int j = 0; j < n; ++j) {  // the order is important
dp[j] = nums1[i] == nums2[j] ? dp[j + 1] + 1 : 0;
ans = max(ans, dp[j]);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int findLength(int[] nums1, int[] nums2) {
final int m = nums1.length;
final int n = nums2.length;
int ans = 0;
int[] dp = new int[n + 1];

for (int i = m - 1; i >= 0; --i)
for (int j = 0; j < n; ++j) { // the order is important
dp[j] = nums1[i] == nums2[j] ? dp[j + 1] + 1 : 0;
ans = Math.max(ans, dp[j]);
}

return ans;
}
}
``````

## Python

``````class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
ans = 0
dp = [0] * (len(nums2) + 1)

for a in reversed(nums1):
for j, b in enumerate(nums2):
dp[j] = dp[j + 1] + 1 if a == b else 0
ans = max(ans, dp[j])

return ans
``````