Maximum Sum Problem
You are given a number N that can be broken into three parts N / 2, N / 3, and N / 4 (considering only integer parts). Each number obtained in this process can be divided further recursively. Your task is to find the maximum sum that can be obtained by summing up the divided parts together.
Note:
The maximum sum may be obtained without dividing N also.
For example :
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.
Input format :
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.
Output format :
For each test case, in a separate line, print a single integer which is the maximum sum.
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints:
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.
- Check for the base condition if the number is 1 or 0 return it.
- Else, recursively call the function for N/2, N/3, and N/4.
- Calculate the sum of these numbers obtained from the above step.
- Return the maximum of N and the sum obtained in the above step.
We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. The idea is to store the sum which already occurred in the previous calls. For this, we will use an array to store previous sums.
Let us understand by example.
Let N = 12
As we can see, some subproblems are called multiple times.
The same subproblems are shown by the same color.
That’s why we are storing the solved subproblems in a map so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the map.
- Use an array dp to store the values of calls that are called for the first time, declare this array globally.
- Now inside the function check for the base condition if the number is 1 or 0 return it.
- Now, check if we already have that value in the array dp then just return that value i.e. if(dp[N] != 0) return dp[N];
- Else recursively call the function for N/2, N/3, and N/4.
- Calculate the sum of these numbers obtained from the above step.
- Store the maximum of sum and number N in array dp i.e. dp[N] = max(sum, N);
We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. The idea is to store the sum which already occurred in the previous calls. For this, we will use an array to store previous sums.
- Declare an array dp of length N+1.
- Initialize dp[0] = 0, dp[1] = 1 as these are base cases.
- Run a loop from i = 2 to N.
- Update the array dp i.e. dp[i] = max(dp[i/2] + dp[i/3] + dp[i/4], i)
- Finally, return dp[N].
