Find the maximum number of composite summands of a number | Java 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
class GFG { static int maxn = 16 ; static int [ ] precompute ( ) { int dp [ ] = new int [ maxn ] , arr [ ] = { 4 , 6 , 9 } ; for ( int i = 0 ; i < maxn ; i ++ ) dp [ i ] = - 1 ; dp [ 0 ] = 0 ; for ( int i = 1 ; i < maxn ; ++ i ) { for ( int k = 0 ; k < 3 ; k ++ ) { int j = arr [ k ] ; if ( i >= j && dp [ i - j ] != - 1 ) { dp [ i ] = Math . max ( dp [ i ] , dp [ i - j ] + 1 ) ; } } } return dp ; } static int Maximum_Summands ( int [ ] dp , int n ) { if ( n < maxn ) return dp [ n ] ; else { int t = ( n - maxn ) / 4 + 1 ; return t + dp [ n - 4 * t ] ; } } public static void main ( String args [ ] ) { int n = 12 ; int [ ] dp = precompute ( ) ; System . out . println ( Maximum_Summands ( dp , n ) ) ; } }