Longest Common Subsequence with at most k changes allowed | Javascript program to find LCS of two arrays with k changes allowed in first array . ; Return LCS with at most k changes allowed . ; If at most changes is less than 0. ; If any of two array is over . ; Making a reference variable to dp [ n ] [ m ] [ k ] ; If value is already calculated , return that value . ; Calculating LCS with no changes made . ; Calculating LCS when array element are same . ; Calculating LCS with changes made . ; Driver Code
let MAX = 10 ; function lcs ( dp , arr1 , n , arr2 , m , k ) { if ( k < 0 ) return - 10000000 ; if ( n < 0 m < 0 ) return 0 ; let ans = dp ; if ( ans != - 1 ) return ans ; try { ans = Math . max ( lcs ( dp , arr1 , n - 1 , arr2 , m , k ) , lcs ( dp , arr1 , n , arr2 , m - 1 , k ) ) ; if ( arr1 [ n - 1 ] == arr2 [ m - 1 ] ) ans = Math . max ( ans , 1 + lcs ( dp , arr1 , n - 1 , arr2 , m - 1 , k ) ) ; ans = Math . max ( ans , 1 + lcs ( dp , arr1 , n - 1 , arr2 , m - 1 , k - 1 ) ) ; } catch ( e ) { } return ans ; } let k = 0 ; let arr1 = [ 1 , 2 , 3 , 4 , 5 ] ; let arr2 = [ 5 , 3 , 1 , 4 , 2 ] ; let n = arr1 . length ; let m = arr2 . length ; let dp = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) for ( let j = 0 ; j < MAX ; j ++ ) for ( let l = 0 ; l < MAX ; l ++ ) dp = - 1 ; document . write ( lcs ( dp , arr1 , n , arr2 , m , k ) ) ;