Code is like humor. When you have to explain it, it's bad
-Cory House
MAXIMUM LENGTH OF REPEATED SUBARRAY
Hey coder. We hope you have been able to understand the previous problems of dynamic programming. In this article, we will discuss the question, "Maximum Length of Repeated Subarray".
We suggest you go through the problem's outline before moving any further.
You are given two arrays of integers arr1 and arr2.
You have to find the maximum length of the subarray that appears in both the given arrays.
Approach
WHAT
To understand this problem we take the example where arr1= [5,4,3,2,1] and arr2= [7,8,4,3,2,5]. Here the longest repeating subarray is [4,3,2] of length 3.
Reader, did you notice that this question is very similar to the problem "Longest Common Substring". If you haven't checked it out, we suggest you do it now.
We directly start making a 2d dp array of dimensions (arr1.length+1)*(arr2.length+1).
For each cell, we compare the corresponding prefixe of arr1 with the corresponding prefixe of arr2 and find their longest common suffix. The length of this longest common suffix will be stored in the cell.
In figure 2, for the marked cell, the corresponding prefixes for the cell are [5,4,3] and [7,8,4,3]. The longest common suffix for these prefixes is [4,3] which is of length 2. Hence 2 is stored in the marked cell.
If the end elements of the two prefixes are not the same as shown in figure 3, we can directly say that the length of their common suffix is 0.
Else if the end elements are the same as shown in figure 4, then we compare the last elements of the array before it. The answer for this problem is stored in the cell corresponding to the prefixes [5,4] and [7,8,4].
Hence the final answer is 1 added to the length stored in the immediate northwest cell.
We now start filling our array.
For the first row and the first column, if even one of the prefixes is a blank, then 0 is stored in the corresponding cells.
Also, we follow the rules in the previous 2 points which gives us figure 5.
We want you to fill the rest of the array yourself and check the answer with figure 6.
Our desired answer is the maximum value of length in the array which is 3.
Reader, after coding many problems of dynamic programming we trust that you can write the code for this question yourself.
You can check your answer with the code given below.
import java.io.*;
import java.util.*;
public class Main {
public static int solution(int[] arr1, int[] arr2) {
int[][]dp=new int[arr1.length+1][arr2.length+1];
int ans=0;
for(int i=1;i < dp.length;i++){
for(int j=1;j < dp[0].length;j++){
if(arr1[i-1]==arr2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
ans=Math.max(ans,dp[i][j]);
}
}
return ans;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr1 = new int[n];
for (int i = 0 ; i < n; i++) {
arr1[i] = scn.nextInt();
}
int m = scn.nextInt();
int[] arr2 = new int[m];
for (int i = 0 ; i < m; i++) {
arr2[i] = scn.nextInt();
}
System.out.println(solution(arr1, arr2));
}
}
java;
true";
Analysis
TIME COMPLEXITY- O(n2)
SPACE COMPLEXITY- O(n2)
We conclude the problem here. In case you had any difficulties, we highly recommend you to watch the solution video too.
