Find the maximum number of composite summands of a number | JavaScript implementation of the above approach ; Function to generate the dp array ; combination of three integers ; take the maximum number of summands ; Function to find the maximum number of summands ; If n is a smaller number , less than 16 return dp [ n ] ; Else , find a minimal number t as explained in solution ; Driver code ; Generate dp array
let maxn = 16 ; function precompute ( ) { let dp = new Array ( maxn ) ; let arr = [ 4 , 6 , 9 ] ; for ( let i = 0 ; i < maxn ; i ++ ) dp [ i ] = - 1 ; dp [ 0 ] = 0 ; for ( let i = 1 ; i < maxn ; ++ i ) { for ( let k = 0 ; k < 3 ; k ++ ) { let j = arr [ k ] ; if ( i >= j && dp [ i - j ] != - 1 ) { dp [ i ] = Math . max ( dp [ i ] , dp [ i - j ] + 1 ) ; } } } return dp ; } function Maximum_Summands ( dp , n ) { if ( n < maxn ) return dp [ n ] ; else { let t = parseInt ( ( n - maxn ) / 4 , 10 ) + 1 ; return t + dp [ n - 4 * t ] ; } } let n = 12 ; $n = 12 ; let dp = precompute ( ) ; document . write ( Maximum_Summands ( dp , n ) ) ;