Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 20 minutes | Coding time: 5 minutes

This question is a simple yet confusing problem, and can be asked during a programming interview.

Given a number n, we can divide it in only three parts n/2, n/3 and n/4 recursively (considering only integer part). We have to find the maximum sum that can be made by summing those three parts (n/2 + n/3 + n/4) together.

We will solve this problem in 2 ways:

- Recursive approach O(3^N)
- Dynamic Programming O(N)

For example:

```
Given n = 16, output is 17,
as we divide it in three parts, we get
{16/2, 16/3, 16/4} = {8, 5, 4}
Its sum is = 8 + 5 + 4 = 17,
now again we break them further,
{8/2, 8/3, 8/4} = {4, 2, 2}, its sum is 8
and further breaking them will end in getting 1 as maximum sum,
thus 8 can give maximum sum as 8 only
Similarly for 5 and 4 also we will be getting 5 and 4 respectively as maximum sum, thus the maximum sum we can get by breaking 16 is 8 + 5 + 4 = 17.
```

### Approach 1 : Recursion

A simple and easy method to solve this problem can be breaking the number recursively and checking to get the maximum sum. We can find, **max((break(n/2) + break(n/3) + break(n/4)), n)** and return it, break(n) is the function used recursively. It will work, as either the sum of the parts would be maximum or the number itself would be maximum.

### Pseudocode

```
1) Check the number for base condition of 0 and 1.
2) Call the function recursively for all three parts.
3) Return the maximum of sum or the number itself.
```

#### Recursive Implementation

```
# Function to find the maximum sum
def break(n) :
# number should be atleast greater than 2 for recursive calls
if (n == 0 or n == 1) :
return n
# recursively breaking the number and getting maximum as result
return max((break(n // 2) + break(n // 3) + break(n // 4)), n)
# Calling the funtion
n = 16
print(break(n))
```

### Approach 2 : Dynamic Programming

The recursive approach was very simple, but in terms of **efficiency** it was not best as while breaking the function recursively we were doing some of the operations multiple times. For example : while calculating result for 16, we called the funtion twice for n=4 (one for 16//4 part and another for 8//2 part), we can avoid this problem by using **Dynamic Programming**. We can store the result obtained for a number in an array and can invoke that result whenever we find that number again.

### Pseudocode

```
1) Initialise the array for size (n+1).
2) Fill the value of base cases inside array
3) Iterate through n and find result for each, retrieving values required from the array
4) Return thr value at position n inside array.
```

#### Dynamic programming Implementation

```
# Function to find the maximum sum
def break(n):
# Initialing an array
stored = [0]*(n+1)
# base conditions covered
stored[0] = 0
stored[1] = 1
# Using bottom-up method to fill array
for i in range(2, n+1):
stored[i] = max(stored[int(i//2)] + stored[int(i/3)] + stored[int(i/4)], i);
return dp[n]
# Calling the funtion
n = 16
print(break(n))
```

### Complexity

The time and space complexity of Dynamic Programming approach are:

- Time Complexity : O(n)
- Space Complexity : O(n) in case of Dynamic programming
- where n is given integer

The time and space complexity of recursive approach are:

- Time Complexity : O(2^n)
- Space Complexity : O(1) in case of Dynamic programming
- where n is given integer

## Question

#### What is the downside of Dynamic programming ?

Further interesting Dynamic Programming Questions to solve