## Thursday, November 17, 2016

### Recursively break a number in 3 parts to get maximum sum - GeeksforGeeks

Recursively break a number in 3 parts to get maximum sum - GeeksforGeeks
Given a number n, we can divide it in only three parts n/2, n/3 and n/4 (we will consider only integer part). The task is to find the maximum sum we can make by dividing number in three parts recursively and summing up them together.

simple solution for this problem is to do it recursively. In each call we have to check only max((max(n/2) + max(n/3) + max(n/4)), n) and return it. Because either we can get maximum sum by breaking number in parts or number is itself maximum
`int` `breakSum(``int` `n)`
`{`
`    ``// base conditions`
`    ``if` `(n==0 || n == 1)`
`        ``return` `n;`

`    ``// recursively break the number and return`
`    ``// what maximum you can get`
`    ``return` `max((breakSum(n/2) + breakSum(n/3) +`
`                ``breakSum(n/4)),  n);`
`}`

`int` `breakSum(``int` `n)`
`{`
`    ``int` `dp[n+1];`

`    ``// base conditions`
`    ``dp[0] = 0, dp[1] = 1;`

`    ``// Fill in bottom-up manner using recursive`
`    ``// formula.`
`    ``for` `(``int` `i=2; i<=n; i++)`
`       ``dp[i] = max(dp[i/2] + dp[i/3] + dp[i/4], i);`

`    ``return` `dp[n];`
`}`
Read full article from Recursively break a number in 3 parts to get maximum sum - GeeksforGeeks