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 Codeint 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
// Java program// for the above approachimport 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)); }} |
Python3
# Python program# for the above approach# Function to find the length of the# longest subarray in arr1 which# is a subsequence in arr2def 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 Codeif __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#
// C# program for the above approachusing 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 Codestatic 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 |
Javascript
<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> |
Output
3
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 Codeint 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
// Java program for the above approachimport 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 Codepublic 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));}} |
Python3
# 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 Codeif __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)) |
Output
3
Time Complexity: O(M * N)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
