Minimize elements to be added to a given array such that it contains another given array as its subsequence | Set 2 | C # program for the above approach ; Function to return minimum element to be added in array B so that array A become subsequence of array B ; Stores indices of the array elements ; Iterate over the array ; Store the indices of the array elements ; Stores the LIS ; Check if element B [ i ] is in array [ ] A ; Perform Binary Search ; Find the value of mid m ; Update l and r ; If found better element ' e ' for pos r + 1 ; Otherwise , extend the current subsequence ; Return the answer ; Driver Code ; Given arrays ; Function Call
using System ; using System . Collections . Generic ; class GFG { static int minElements ( int [ ] A , int [ ] B , int N , int M ) { Dictionary < int , int > map = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < A . Length ; i ++ ) { map . Add ( A [ i ] , i ) ; } List < int > subseq = new List < int > ( ) ; int l = 0 , r = - 1 ; for ( int i = 0 ; i < M ; i ++ ) { if ( map . ContainsKey ( B [ i ] ) ) { int e = map [ B [ i ] ] ; while ( l <= r ) { int m = l + ( r - l ) / 2 ; if ( subseq [ m ] < e ) l = m + 1 ; else r = m - 1 ; } if ( r + 1 < subseq . Count ) { subseq [ r + 1 ] = e ; } else { subseq . Add ( e ) ; } l = 0 ; r = subseq . Count - 1 ; } } return N - subseq . Count ; } public static void Main ( String [ ] args ) { int [ ] A = { 1 , 2 , 3 , 4 , 5 } ; int [ ] B = { 2 , 5 , 6 , 4 , 9 , 12 } ; int M = A . Length ; int N = B . Length ; Console . WriteLine ( minElements ( A , B , M , N ) ) ; } }