```
def max(a,b):
if a > b :
return a
else:
return b
def maximumValue(coinNumber):
if (coinNumber <= 4 and coinNumber >= 0):
return coinNumber
else:
return max(coinNumber, maximumValue(coinNumber//2) + maximumValue(coinNumber//3) + maximumValue(coinNumber//4))
while True:
try:
coinNumber = int(input())
print(maximumValue(coinNumber))
except:
break
```

I guess some part of your code is missing. What you wrote is a brute-force solution, whose time-complexity is Exponential.

The Problem can be easily solved using Dynamic Programming. I am not gonna give hint, just try it yourself.

Please elaborate the concept you used.

Okay, letâ€™s say you have this test case

```
N = 144
```

Then, your code runs in this fashion, probably.

```
144 (max(144, 72 + 48 + 36)
/ | \
/ | \
/ | \
max(72, 36+24+18) 72 48 36 max(36, 18+12+9)
/ | \ / | \ / | \
36 24 18 24 16 12 18 12 9
................................
and it goes on
```

As you can observe, in the process of calculating Maximum Value for 144, you calculated the same for 72, 48 and 36,â€¦, to calculate same for 72, you calculate same for 36, 24, 18,â€¦, to calculate same for 48, you calculate same for 24, 16, 12, to calculate same for 36, you calculate same for 18, 12, 9 and â€¦

**YOU ARE REPEATING YOUR SELF**

To avoid repeating, youâ€™ll store the values calculated so far somewhere ( may be an array, or hash set, or a dictionary).

Now, this is called Dynamic Programming.

This is a Programming Paradigm used to reduce the time complexity of most of the problems, whose time complexity is exponential (c^n) when solved using brute-force, and involve repeated calculations like the above problem.

Hereâ€™s what a typical Python Solution looks like:

```
dp = dict()
def solve(n):
if n == 0:
return 0
try:
r = dp[n]
except:
c = max(n, solve(n//2) + solve(n//3) + solve(n//4))
dp[n] = c
r = c
return r
def main():
while True:
try:
n = int(input())
print(solve(n))
except:
break
main()
```

Explanation:

- First, we initialise a dictionary, which stores key-value pair
- In this case, key is N and value is the solution for N
- Initially, this dictionary has nothing
- But, we dynamically calculate the solution for Nâ€™s as we progress
- For each test case, we do the following:

- Read N
- Check if we have calculated the solution for this N (using â€śtry-catchâ€ť or â€śinâ€ť in Python).
- If we have calculated, simply return the solution
- Else, solution for this N will be max(N, N/2 + N/3 + N/4). So, we will recursively calculate the solutions for N/2, N/3 and N/4 by repeating the steps 2,3 in similar fashion.
- Now, after you calculate the solution for N, donâ€™t forget to store it in the dicionary.

Note that the maximum recursion depth will be log_2 (N), since the smallest number dividing the N is 2.

Hope this is clear, and this is the best way I can explain.

Cheers

I didnâ€™t thought that somebody can explain DP such easily. I learnt the concept. Thanksâ€¦