Longest Common Subsequence of two arrays out of which one array consists of distinct elements only | C ++ program to to implement the above approach ; Function to find the Longest Common Subsequence between the two arrays ; Maps elements of firstArr [ ] to their respective indices ; Traverse the array firstArr [ ] ; Stores the indices of common elements between firstArr [ ] and secondArr [ ] ; Traverse the array secondArr [ ] ; If current element exists in the Map ; Stores lIS from tempArr [ ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LCS ( vector < int > & firstArr , vector < int > & secondArr ) { unordered_map < int , int > mp ; for ( int i = 0 ; i < firstArr . size ( ) ; i ++ ) { mp [ firstArr [ i ] ] = i + 1 ; } vector < int > tempArr ; for ( int i = 0 ; i < secondArr . size ( ) ; i ++ ) { if ( mp . find ( secondArr [ i ] ) != mp . end ( ) ) { tempArr . push_back ( mp [ secondArr [ i ] ] ) ; } } vector < int > tail ; tail . push_back ( tempArr [ 0 ] ) ; for ( int i = 1 ; i < tempArr . size ( ) ; i ++ ) { if ( tempArr [ i ] > tail . back ( ) ) tail . push_back ( tempArr [ i ] ) ; else if ( tempArr [ i ] < tail [ 0 ] ) tail [ 0 ] = tempArr [ i ] ; else { auto it = lower_bound ( tail . begin ( ) , tail . end ( ) , tempArr [ i ] ) ; * it = tempArr [ i ] ; } } return ( int ) tail . size ( ) ; } int main ( ) { vector < int > firstArr = { 3 , 5 , 1 , 8 } ; vector < int > secondArr = { 3 , 3 , 5 , 3 , 8 } ; cout << LCS ( firstArr , secondArr ) ; return 0 ; }