Maximize sum by selecting X different | Store overlapping subproblems of the recurrence relation ; Function to find maximum sum of at most N with different index array elements such that at most X are from A [ ] , Y are from B [ ] and Z are from C [ ] ; Base Cases ; If the subproblem already computed ; Selecting i - th element from A [ ] ; Selecting i - th element from B [ ] ; Selecting i - th element from C [ ] ; i - th elements not selected from any of the arrays ; Select the maximum sum from all the possible calls ; Given X , Y and Z ; Given A [ ] ; Given B [ ] ; Given C [ ] ; Given Size ; Function Call
let dp = new Array ( 50 ) ; function FindMaxS ( X , Y , Z , n , A , B , C ) { if ( X < 0 Y < 0 Z < 0 ) return Number . MIN_VALUE ; if ( n < 0 ) return 0 ; if ( dp [ n ] [ X ] [ Y ] [ Z ] != - 1 ) { return dp [ n ] [ X ] [ Y ] [ Z ] ; } let ch = A [ n ] + FindMaxS ( X - 1 , Y , Z , n - 1 , A , B , C ) ; let ca = B [ n ] + FindMaxS ( X , Y - 1 , Z , n - 1 , A , B , C ) ; let co = C [ n ] + FindMaxS ( X , Y , Z - 1 , n - 1 , A , B , C ) ; let no = FindMaxS ( X , Y , Z , n - 1 , A , B , C ) ; let maximum = Math . max ( ch , Math . max ( ca , Math . max ( co , no ) ) ) ; dp [ n ] [ X ] [ Y ] [ Z ] = maximum ; return dp [ n ] [ X ] [ Y ] [ Z ] ; } let X = 1 ; let Y = 1 ; let Z = 1 ; let A = [ 10 , 0 , 5 ] ; let B = [ 5 , 10 , 0 ] ; let C = [ 0 , 5 , 10 ] ; let n = B . length ; for ( let i = 0 ; i < 50 ; i ++ ) { dp [ i ] = new Array ( 50 ) ; for ( let j = 0 ; j < 50 ; j ++ ) { dp [ i ] [ j ] = new Array ( 50 ) ; for ( let k = 0 ; k < 50 ; k ++ ) { dp [ i ] [ j ] [ k ] = new Array ( 50 ) ; for ( let l = 0 ; l < 50 ; l ++ ) { dp [ i ] [ j ] [ k ] [ l ] = - 1 ; } } } } document . write ( FindMaxS ( X , Y , Z , n - 1 , A , B , C ) ) ;