The maximum sum may be obtained without dividing N also.
N = 12 breaking N into three parts will give 6, 4, and 3 which gives us the sum = 13. Further breaking 6, 4, and 3 into other parts will give us a sum less than or equal to 6, 4, and 3 respectively. Therefore, the maximum answer will be 13.
The first line of input contains an integer T denoting the number of test cases. The first and the only line of each test case contains a single integer N.
For each test case, in a separate line, print a single integer which is the maximum sum.
You don’t have to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 5 1 <= N <= 3000 Time Limit : 1 sec
The idea is to use recursion in each call. In each call we have two options: either break the number or not. Thus, to explore all the possibilities we will use recursion.