Longest Common Subsequence of two arrays out of which one array consists of distinct elements only | Python3 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
from bisect import bisect_left NEW_LINE def LCS ( firstArr , secondArr ) : NEW_LINE INDENT mp = { } NEW_LINE for i in range ( len ( firstArr ) ) : NEW_LINE INDENT mp [ firstArr [ i ] ] = i + 1 NEW_LINE DEDENT tempArr = [ ] NEW_LINE for i in range ( len ( secondArr ) ) : NEW_LINE INDENT if ( secondArr [ i ] in mp ) : NEW_LINE INDENT tempArr . append ( mp [ secondArr [ i ] ] ) NEW_LINE DEDENT DEDENT tail = [ ] NEW_LINE tail . append ( tempArr [ 0 ] ) NEW_LINE for i in range ( 1 , len ( tempArr ) ) : NEW_LINE INDENT if ( tempArr [ i ] > tail [ - 1 ] ) : NEW_LINE INDENT tail . append ( tempArr [ i ] ) NEW_LINE DEDENT elif ( tempArr [ i ] < tail [ 0 ] ) : NEW_LINE INDENT tail [ 0 ] = tempArr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT it = bisect_left ( tail , tempArr [ i ] ) NEW_LINE it = tempArr [ i ] NEW_LINE DEDENT DEDENT return len ( tail ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT firstArr = [ 3 , 5 , 1 , 8 ] NEW_LINE secondArr = [ 3 , 3 , 5 , 3 , 8 ] NEW_LINE print ( LCS ( firstArr , secondArr ) ) NEW_LINE DEDENT