Longest subarray of an array which is a subsequence in another array
Last Updated : 24 Nov, 2023
Given two arrays arr1[] and arr2[], the task is to find the longest subarray of arr1[] which is a subsequence of arr2[].
Examples:
Input: arr1[] = {4, 2, 3, 1, 5, 6}, arr2[] = {3, 1, 4, 6, 5, 2}
Output: 3
Explanation: The longest subarray of arr1[] which is a subsequence in arr2[] is {3, 1, 5}
Input: arr1[] = {3, 2, 4, 7, 1, 5, 6, 8, 10, 9}, arr2[] = {9, 2, 4, 3, 1, 5, 6, 8, 10, 7}
Output: 5
Explanation: The longest subarray in arr1[] which is a subsequence in arr2[] is {1, 5, 6, 8, 10}.
Approach: The idea is to use Dynamic Programming to solve this problem. Follow the steps below to solve the problem:
- Initialize a DP[][] table, where DP[i][j] stores the length of the longest subarray up to the ith index in arr1[] which is a subsequence in arr2[] up to the jth index.
- Now, traverse over both the arrays and perform the following:
- Case 1: If arr1[i] and arr2[j] are equal, add 1 to DP[i - 1][j - 1] as arr1[i] and arr2[j] contribute to the required length of the longest subarray.
- Case 2: If arr1[i] and arr2[j] are not equal, set DP[i][j] = DP[i - 1][j].
- Finally, print the maximum value present in DP[][] table as the required answer.
Below is the implementation of the above approach:
C++ // C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of the // longest subarray in arr1[] which // is a subsequence in arr2[] int LongSubarrSeq(int arr1[], int arr2[], int M, int N) { // Length of the array arr1[] // Length of the required // longest subarray int maxL = 0; // Initialize DP[]array int DP[M + 1][N + 1]; // Traverse array arr1[] for (int i = 1; i <= M; i++) { // Traverse array arr2[] for (int j = 1; j <= N; j++) { if (arr1[i - 1] == arr2[j - 1]) { // arr1[i - 1] contributes to // the length of the subarray DP[i][j] = 1 + DP[i - 1][j - 1]; } // Otherwise else { DP[i][j] = DP[i][j - 1]; } } } // Find the maximum value // present in DP[][] for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { maxL = max(maxL, DP[i][j]); } } // Return the result return maxL; } // Driver Code int main() { int arr1[] = { 4, 2, 3, 1, 5, 6 }; int M = sizeof(arr1) / sizeof(arr1[0]); int arr2[] = { 3, 1, 4, 6, 5, 2 }; int N = sizeof(arr2) / sizeof(arr2[0]); // Function call to find the length // of the longest required subarray cout << LongSubarrSeq(arr1, arr2, M, N) <<endl; return 0; } // This code is contributed by code_hunt. // Java program // for the above approach import java.io.*; class GFG { // Function to find the length of the // longest subarray in arr1[] which // is a subsequence in arr2[] private static int LongSubarrSeq( int[] arr1, int[] arr2) { // Length of the array arr1[] int M = arr1.length; // Length of the array arr2[] int N = arr2.length; // Length of the required // longest subarray int maxL = 0; // Initialize DP[]array int[][] DP = new int[M + 1][N + 1]; // Traverse array arr1[] for (int i = 1; i <= M; i++) { // Traverse array arr2[] for (int j = 1; j <= N; j++) { if (arr1[i - 1] == arr2[j - 1]) { // arr1[i - 1] contributes to // the length of the subarray DP[i][j] = 1 + DP[i - 1][j - 1]; } // Otherwise else { DP[i][j] = DP[i][j - 1]; } } } // Find the maximum value // present in DP[][] for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { maxL = Math.max(maxL, DP[i][j]); } } // Return the result return maxL; } // Driver Code public static void main(String[] args) { int[] arr1 = { 4, 2, 3, 1, 5, 6 }; int[] arr2 = { 3, 1, 4, 6, 5, 2 }; // Function call to find the length // of the longest required subarray System.out.println(LongSubarrSeq(arr1, arr2)); } } # Python program # for the above approach # Function to find the length of the # longest subarray in arr1 which # is a subsequence in arr2 def LongSubarrSeq(arr1, arr2): # Length of the array arr1 M = len(arr1); # Length of the array arr2 N = len(arr2); # Length of the required # longest subarray maxL = 0; # Initialize DParray DP = [[0 for i in range(N + 1)] for j in range(M + 1)]; # Traverse array arr1 for i in range(1, M + 1): # Traverse array arr2 for j in range(1, N + 1): if (arr1[i - 1] == arr2[j - 1]): # arr1[i - 1] contributes to # the length of the subarray DP[i][j] = 1 + DP[i - 1][j - 1]; # Otherwise else: DP[i][j] = DP[i][j - 1]; # Find the maximum value # present in DP for i in range(M + 1): # Traverse array arr2 for j in range(1, N + 1): maxL = max(maxL, DP[i][j]); # Return the result return maxL; # Driver Code if __name__ == '__main__': arr1 = [4, 2, 3, 1, 5, 6]; arr2 = [3, 1, 4, 6, 5, 2]; # Function call to find the length # of the longest required subarray print(LongSubarrSeq(arr1, arr2)); # This code contributed by shikhasingrajput
// C# program for the above approach using System; class GFG{ // Function to find the length of the // longest subarray in arr1[] which // is a subsequence in arr2[] private static int LongSubarrSeq(int[] arr1, int[] arr2) { // Length of the array arr1[] int M = arr1.Length; // Length of the array arr2[] int N = arr2.Length; // Length of the required // longest subarray int maxL = 0; // Initialize DP[]array int[,] DP = new int[M + 1, N + 1]; // Traverse array arr1[] for(int i = 1; i <= M; i++) { // Traverse array arr2[] for(int j = 1; j <= N; j++) { if (arr1[i - 1] == arr2[j - 1]) { // arr1[i - 1] contributes to // the length of the subarray DP[i, j] = 1 + DP[i - 1, j - 1]; } // Otherwise else { DP[i, j] = DP[i, j - 1]; } } } // Find the maximum value // present in DP[][] for(int i = 1; i <= M; i++) { for(int j = 1; j <= N; j++) { maxL = Math.Max(maxL, DP[i, j]); } } // Return the result return maxL; } // Driver Code static public void Main() { int[] arr1 = { 4, 2, 3, 1, 5, 6 }; int[] arr2 = { 3, 1, 4, 6, 5, 2 }; // Function call to find the length // of the longest required subarray Console.WriteLine(LongSubarrSeq(arr1, arr2)); } } // This code is contributed by susmitakundugoaldanga <script> // javascript program of the above approach // Function to find the length of the // longest subarray in arr1[] which // is a subsequence in arr2[] function LongSubarrSeq( arr1, arr2) { // Length of the array arr1[] let M = arr1.length; // Length of the array arr2[] let N = arr2.length; // Length of the required // longest subarray let maxL = 0; // Initialize DP[]array let DP = new Array(M + 1); // Loop to create 2D array using 1D array for (var i = 0; i < DP.length; i++) { DP[i] = new Array(2); } for (var i = 0; i < DP.length; i++) { for (var j = 0; j < DP.length; j++) { DP[i][j] = 0; } } // Traverse array arr1[] for (let i = 1; i <= M; i++) { // Traverse array arr2[] for (let j = 1; j <= N; j++) { if (arr1[i - 1] == arr2[j - 1]) { // arr1[i - 1] contributes to // the length of the subarray DP[i][j] = 1 + DP[i - 1][j - 1]; } // Otherwise else { DP[i][j] = DP[i][j - 1]; } } } // Find the maximum value // present in DP[][] for (let i = 1; i <= M; i++) { for (let j = 1; j <= N; j++) { maxL = Math.max(maxL, DP[i][j]); } } // Return the result return maxL; } // Driver Code let arr1 = [ 4, 2, 3, 1, 5, 6 ]; let arr2 = [ 3, 1, 4, 6, 5, 2 ]; // Function call to find the length // of the longest required subarray document.write(LongSubarrSeq(arr1, arr2)); </script> Time Complexity: O(M * N)
Auxiliary Space: O(M * N)
Efficient Approach: Space optimization: In the previous approach the current value dp[i][j] only depends upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size n+1.
- Initialize a variable maxi to store the final answer and update it by iterating through the Dp.
- Set a base case by initializing the values of DP.
- Now iterate over subproblems with the help of a nested loop and get the current value from previous computations.
- Now Create variables prev, temp used to store the previous values from previous computations.
- After every iteration assign the value of temp to temp for further iteration.
- At last return and print the final answer stored in maxi.
Implementation:
C++ // C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of the // longest subarray in arr1[] // which is a subsequence in arr2[] int LongSubarrSeq(int arr1[], int arr2[], int M, int N) { // to store final result int maxL = 0; // to store previous computations // Initialize DP[] vector vector<int> DP(N + 1, 0); // iterate over subproblems to get the // current value from previous computations for (int i = 1; i <= M; i++) { int prev = 0; for (int j = 1; j <= N; j++) { // Store current DP[j] value int temp = DP[j]; if (arr1[i - 1] == arr2[j - 1]) { DP[j] = 1 + prev; maxL = max(maxL, DP[j]); } else { DP[j] = DP[j - 1]; } // Update previous DP[j] value prev = temp; } } // Return final answer return maxL; } // Driver Code int main() { int arr1[] = { 4, 2, 3, 1, 5, 6 }; int M = sizeof(arr1) / sizeof(arr1[0]); int arr2[] = { 3, 1, 4, 6, 5, 2 }; int N = sizeof(arr2) / sizeof(arr2[0]); cout << LongSubarrSeq(arr1, arr2, M, N); return 0; } // Java program for the above approach import java.util.*; public class Main { // Function to find the length of the // longest subarray in arr1[] // which is a subsequence in arr2[] static int LongSubarrSeq(int arr1[], int arr2[], int M, int N) { // to store final result int maxL = 0; // to store previous computations // Initialize DP[] vector int DP[] = new int[N + 1]; Arrays.fill(DP, 0); // iterate over subproblems to get the // current value from previous computations for (int i = 1; i <= M; i++) { int prev = 0; for (int j = 1; j <= N; j++) { // Store current DP[j] value int temp = DP[j]; if (arr1[i - 1] == arr2[j - 1]) { DP[j] = 1 + prev; maxL = Math.max(maxL, DP[j]); } else { DP[j] = DP[j - 1]; } // Update previous DP[j] value prev = temp; } } // Return final answer return maxL; } // Driver Code public static void main(String[] args) { int arr1[] = { 4, 2, 3, 1, 5, 6 }; int M = arr1.length; int arr2[] = { 3, 1, 4, 6, 5, 2 }; int N = arr2.length; System.out.print(LongSubarrSeq(arr1, arr2, M, N)); } } # Function to find the length of the # longest subarray in arr1[] # which is a subsequence in arr2[] def LongSubarrSeq(arr1, arr2, M, N): # To store the final result maxL = 0 # To store previous computations # Initialize DP[] list DP = [0] * (N + 1) # Iterate over subproblems to get the # current value from previous computations for i in range(1, M + 1): prev = 0 for j in range(1, N + 1): # Store current DP[j] value temp = DP[j] if arr1[i - 1] == arr2[j - 1]: DP[j] = 1 + prev maxL = max(maxL, DP[j]) else: DP[j] = DP[j - 1] # Update previous DP[j] value prev = temp # Return the final answer return maxL # Driver Code if __name__ == "__main__": arr1 = [4, 2, 3, 1, 5, 6] M = len(arr1) arr2 = [3, 1, 4, 6, 5, 2] N = len(arr2) print(LongSubarrSeq(arr1, arr2, M, N))
using System; class Program { // Function to find the length of the // longest subarray in arr1[] // which is a subsequence in arr2[] static int LongSubarrSeq(int[] arr1, int[] arr2, int M, int N) { // to store final result int maxL = 0; // to store previous computations // Initialize DP[] array int[] DP = new int[N + 1]; // iterate over subproblems to get the // current value from previous computations for (int i = 1; i <= M; i++) { int prev = 0; for (int j = 1; j <= N; j++) { // Store current DP[j] value int temp = DP[j]; if (arr1[i - 1] == arr2[j - 1]) { DP[j] = 1 + prev; maxL = Math.Max(maxL, DP[j]); } else { DP[j] = DP[j - 1]; } // Update previous DP[j] value prev = temp; } } // Return final answer return maxL; } // Driver Code static void Main() { int[] arr1 = { 4, 2, 3, 1, 5, 6 }; int M = arr1.Length; int[] arr2 = { 3, 1, 4, 6, 5, 2 }; int N = arr2.Length; Console.WriteLine(LongSubarrSeq(arr1, arr2, M, N)); } } // Function to find the length of the // longest subarray in arr1[] // which is a subsequence in arr2[] function LongSubarrSeq(arr1, arr2, M, N) { // to store final result let maxL = 0; // to store previous computations // Initialize DP[] array let DP = new Array(N + 1).fill(0); // iterate over subproblems to get the // current value from previous computations for (let i = 1; i <= M; i++) { let prev = 0; for (let j = 1; j <= N; j++) { // Store current DP[j] value let temp = DP[j]; if (arr1[i - 1] === arr2[j - 1]) { DP[j] = 1 + prev; maxL = Math.max(maxL, DP[j]); } else { DP[j] = DP[j - 1]; } // Update previous DP[j] value prev = temp; } } // Return final answer return maxL; } // Driver Code let arr1 = [4, 2, 3, 1, 5, 6]; let M = arr1.length; let arr2 = [3, 1, 4, 6, 5, 2]; let N = arr2.length; console.log(LongSubarrSeq(arr1, arr2, M, N)); Time Complexity: O(M * N)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Similar Reads
Length of the longest increasing subsequence which does not contain a given sequence as Subarray Given two arrays arr[] and arr1[] of lengths N and M respectively, the task is to find the longest increasing subsequence of array arr[] such that it does not contain array arr1[] as subarray. Examples: Input: arr[] = {5, 3, 9, 3, 4, 7}, arr1[] = {3, 3, 7}Output: 4Explanation: Required longest incre
14 min read
Longest increasing subsequence which forms a subarray in the sorted representation of the array Given an array arr[] of N integers, the task is to find the length of the longest increasing subsequence such that it forms a subarray when the original array is sorted. Examples: Input: arr[] = { 2, 6, 4, 8, 2, 9 }Output: 3Explanation: Sorted array: {2, 2, 4, 6, 8, 9}All possible non-decreasing seq
11 min read
Find the longest subsequence of a string that is a substring of another string Given two strings X and Y consisting of N and M characters, the task is to find the longest subsequence of a string X which is a substring of the string Y. Examples: Input: X = "ABCD", Y = "ACDBDCD"Output: ACDExplanation:"ACD" is longest subsequence of X which is substring of Y. Input: X = A, Y = AO
10 min read
Print all Longest dividing subsequence in an Array Given an array arr[] of N integers, the task is to print all the element of Longest Dividing Subsequence formed by the given array. If we have more than one sequence with maximum length then print all of them. Examples: Input: arr[] = { 2, 11, 16, 12, 36, 60, 71 } Output: 2 12 36 2 12 60 Explanation
8 min read
Longest Subsequence where index of next element is arr[arr[i] + i] Given an array arr[], the task is to find the maximum length sub-sequence from the array which satisfy the following condition: Any element can be chosen as the first element of the sub-sequence but the index of the next element will be determined by arr[arr[i] + i] where i is the index of the previ
6 min read