Find the maximum number of composite summands of a number | C # 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
using System ; using System . Collections ; class GFG { static int maxn = 16 ; static int [ ] dp = new int [ maxn + 1 ] ; static void precompute ( ) { for ( int i = 0 ; i <= maxn ; i ++ ) dp [ i ] = - 1 ; dp [ 0 ] = 0 ; int [ ] vec = { 4 , 6 , 9 } ; for ( int i = 1 ; i < maxn ; ++ i ) { foreach ( int j in vec ) { if ( i >= j && dp [ i - j ] != - 1 ) { dp [ i ] = Math . Max ( dp [ i ] , dp [ i - j ] + 1 ) ; } } } } static int Maximum_Summands ( int n ) { if ( n < maxn ) return dp [ n ] ; else { int t = ( n - maxn ) / 4 + 1 ; return t + dp [ n - 4 * t ] ; } } static void Main ( ) { int n = 12 ; precompute ( ) ; Console . WriteLine ( Maximum_Summands ( n ) ) ; } }