Maximum number of uncrossed lines between two given arrays | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int uncrossedLines ( int * a , int * b , int n , int m ) { int dp [ n + 1 ] [ m + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= m ; j ++ ) { if ( i == 0 j == 0 ) dp [ i ] [ j ] = 0 ; else if ( a [ i - 1 ] == b [ j - 1 ] ) dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] ; else dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; } } return dp [ n ] [ m ] ; } int main ( ) { int A [ ] = { 3 , 9 , 2 } ; int B [ ] = { 3 , 2 , 9 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int M = sizeof ( B ) / sizeof ( B [ 0 ] ) ; cout << uncrossedLines ( A , B , N , M ) ; return 0 ; }