[LeetCode] 718. Maximum Length of Repeated Subarray

轉自LeetCode

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. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

<Solution>

想法如下

• 這題要用 DP 來解。 用 dp[i][j] 代表 A[i] 和 B[j] 有多長的相同 subarry (包含 A[i] 和 B[j])，用 [5, 7, 8] 和 [2, 7, 8] 來舉例

       2  7  8
    0  0  0  0
5   0  0  0  0
7   0  0  1  0
8   0  0  0  2

• 首先，dp = int[A.length + 1][B.length + 1]，且 dp[i][j] = (A[i-1] == B[j-1]) ? dp[i-1][j-1]  + 1 : 0

• 最後的答案，會是 max(dp[i][j])，所以過程中也要順便紀錄最大值

code 如下

Java

	class Solution {
	public int findLength(int[] A, int[] B) {
	int[][] dp = new int[A.length+1][B.length+1];
	int ans = Integer.MIN_VALUE;
	for(int i = 1; i <= A.length; i++) {
	for(int j = 1; j <= B.length; j++) {
	dp[i][j] = (A[i-1] == B[j-1]) ? dp[i-1][j-1] + 1 : 0;
	ans = Math.max(ans, dp[i][j]);
	}
	}
	return ans;
	}
	}

view raw findLength.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun findLength(nums1: IntArray, nums2: IntArray): Int {
	// dp[i][j] means the max length of repeated subarray from nums1[i] to nums2[j]
	val dp = Array(nums1.size+1) { Array(nums2.size+1) {0} }
	var ans = Int.MIN_VALUE
	for(i in 1..nums1.size) {
	for(j in 1..nums2.size) {
	dp[i][j] = if(nums1[i-1] == nums2[j-1]) dp[i-1][j-1] + 1 else 0
	ans = Math.max(ans, dp[i][j])
	}
	}
	return ans
	}
	}

view raw maximum_length_of_repeated_subarray.kt hosted with ❤ by GitHub