Longest Common Subsequence of two arrays out of which one array consists of distinct elements only | Java 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
import java . util . * ; class GFG { static int LCS ( int [ ] firstArr , int [ ] secondArr ) { HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < firstArr . length ; i ++ ) { mp . put ( firstArr [ i ] , i + 1 ) ; } Vector < Integer > tempArr = new Vector < > ( ) ; for ( int i = 0 ; i < secondArr . length ; i ++ ) { if ( mp . containsKey ( secondArr [ i ] ) ) { tempArr . add ( mp . get ( secondArr [ i ] ) ) ; } } Vector < Integer > tail = new Vector < > ( ) ; tail . add ( tempArr . get ( 0 ) ) ; for ( int i = 1 ; i < tempArr . size ( ) ; i ++ ) { if ( tempArr . get ( i ) > tail . lastElement ( ) ) tail . add ( tempArr . get ( i ) ) ; else if ( tempArr . get ( i ) < tail . get ( 0 ) ) tail . add ( 0 , tempArr . get ( i ) ) ; } return ( int ) tail . size ( ) ; } public static void main ( String [ ] args ) { int [ ] firstArr = { 3 , 5 , 1 , 8 } ; int [ ] secondArr = { 3 , 3 , 5 , 3 , 8 } ; System . out . print ( LCS ( firstArr , secondArr ) ) ; } }