Recursively break a number in 3 parts to get maximum sum | A Dynamic programming based Python 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 run the case
MAX = 1000000 NEW_LINE def breakSum ( n ) : NEW_LINE INDENT dp = [ 0 ] * ( n + 1 ) NEW_LINE dp [ 0 ] = 0 NEW_LINE dp [ 1 ] = 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT dp [ i ] = max ( dp [ int ( i / 2 ) ] + dp [ int ( i / 3 ) ] + dp [ int ( i / 4 ) ] , i ) ; NEW_LINE DEDENT return dp [ n ] NEW_LINE DEDENT n = 24 NEW_LINE print ( breakSum ( n ) ) NEW_LINE