Maximum number of uncrossed lines between two given arrays | Function to count maximum number of uncrossed lines between the two given arrays ; Stores the length of lcs obtained upto every index ; Iterate over first array ; Iterate over second array ; Update value in dp table ; If both characters are equal ; Update the length of lcs ; If both characters are not equal ; Update the table ; Return the answer ; Driver Code ; Given array A [ ] and B [ ] ; Function Call
def uncrossedLines ( a , b , n , m ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( m + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( m + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT elif ( a [ i - 1 ] == b [ j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ n ] [ m ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 3 , 9 , 2 ] NEW_LINE B = [ 3 , 2 , 9 ] NEW_LINE N = len ( A ) NEW_LINE M = len ( B ) NEW_LINE print ( uncrossedLines ( A , B , N , M ) ) NEW_LINE DEDENT