Recursively break a number in 3 parts to get maximum sum | A Dynamic programming based C ++ 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
#include <bits/stdc++.h> NEW_LINE #define MAX  1000000 NEW_LINE using namespace std ; int breakSum ( int n ) { int dp [ n + 1 ] ; dp [ 0 ] = 0 , dp [ 1 ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) dp [ i ] = max ( dp [ i / 2 ] + dp [ i / 3 ] + dp [ i / 4 ] , i ) ; return dp [ n ] ; } int main ( ) { int n = 24 ; cout << breakSum ( n ) ; return 0 ; }