Recursively break a number in 3 parts to get maximum sum | A simple recursive JAVA program to find maximum sum by recursively breaking a number in 3 parts . ; Function to find the maximum sum ; base conditions ; Fill in bottom - up manner using recursive formula . ; Driver program to test the above function
import java . io . * ; class GFG { final int MAX = 1000000 ; static int breakSum ( int n ) { int dp [ ] = new int [ n + 1 ] ; dp [ 0 ] = 0 ; dp [ 1 ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) dp [ i ] = Math . max ( dp [ i / 2 ] + dp [ i / 3 ] + dp [ i / 4 ] , i ) ; return dp [ n ] ; } public static void main ( String [ ] args ) { int n = 24 ; System . out . println ( breakSum ( n ) ) ; } }