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
using System ; using System . Collections . Generic ; public class GFG { static int LCS ( int [ ] firstArr , int [ ] secondArr ) { Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < firstArr . Length ; i ++ ) { mp . Add ( firstArr [ i ] , i + 1 ) ; } List < int > tempArr = new List < int > ( ) ; for ( int i = 0 ; i < secondArr . Length ; i ++ ) { if ( mp . ContainsKey ( secondArr [ i ] ) ) { tempArr . Add ( mp [ secondArr [ i ] ] ) ; } } List < int > tail = new List < int > ( ) ; tail . Add ( tempArr [ 0 ] ) ; for ( int i = 1 ; i < tempArr . Count ; i ++ ) { if ( tempArr [ i ] > tail [ tail . Count - 1 ] ) tail . Add ( tempArr [ i ] ) ; else if ( tempArr [ i ] < tail [ 0 ] ) tail . Insert ( 0 , tempArr [ i ] ) ; } return ( int ) tail . Count ; } public static void Main ( String [ ] args ) { int [ ] firstArr = { 3 , 5 , 1 , 8 } ; int [ ] secondArr = { 3 , 3 , 5 , 3 , 8 } ; Console . Write ( LCS ( firstArr , secondArr ) ) ; } }