# Maximum value with the choice of either dividing or considering as it is

We are given a number n, we need to find the maximum sum possible with the help of following function:
F(n) = max( (F(n/2) + F(n/3) + F(n/4) + F(n/5)), n). To calculate F(n, ) we may either have n as our result or we can further break n into four part as in given function definition. This can be done as much time as we can. Find the maximum possible sum you can get from a given N. Note : 1 can not be break further so F(1) = 1 as a base case.

Examples :

```Input : n = 10
Output : MaxSum = 12
Explanation:
f(10) = f(10/2) + f(10/3) + f(10/4) + f(10/5)
= f(5)  +   f(3)  +  f(2)   +  f(2)
= 12
5, 3 and 2 cannot be further divided.

Input : n = 2
Output : MaxSum = 2
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach : This problem can be solve with recursive approach but that will cost us a high complexity because of its overlapping sub problems. So we apply dynamic programming concept to solve this question in bottom up manner as:

## C++

 `// CPP program for maximize result when ` `// we have choice to divide or consider ` `// as it is. ` `#include ` `using` `namespace` `std; ` ` `  `// function for calculating max possible result ` `int` `maxDP(``int` `n) ` `{ ` `    ``int` `res[n + 1]; ` `    ``res[0] = 0; ` `    ``res[1] = 1; ` ` `  `    ``// Compute remaining values in bottom ` `    ``// up manner. ` `    ``for` `(``int` `i = 2; i <= n; i++) ` `        ``res[i] = max(i, (res[i / 2] + res[i / 3] + res[i / 4] + res[i / 5])); ` ` `  `    ``return` `res[n]; ` `} ` ` `  `// driver program ` `int` `main() ` `{ ` `    ``int` `n = 60; ` `    ``cout << ``"MaxSum ="` `<< maxDP(n); ` `    ``return` `0; ` `} `

## Java

 `// Java program for maximize result when ` `// we have choice to divide or consider ` `// as it is. ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``// function for calculating max ` `    ``// possible result ` `    ``static` `int` `maxDP(``int` `n) ` `    ``{ ` `        ``int` `res[] = ``new` `int``[n + ``1``]; ` `        ``res[``0``] = ``0``; ` `        ``res[``1``] = ``1``; ` ` `  `        ``// Compute remaining values in ` `        ``// bottom up manner. ` `        ``for` `(``int` `i = ``2``; i <= n; i++) ` `            ``res[i] = Math.max(i, (res[i / ``2``] + res[i / ``3``] + res[i / ``4``] + res[i / ``5``])); ` ` `  `        ``return` `res[n]; ` `    ``} ` ` `  `    ``// driver program ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `n = ``60``; ` `        ``System.out.println(``"MaxSum = "` `+ maxDP(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m `

## Python3

 `# Python3 code to maximize result when ` `# we have choice to divide or consider ` `# as it is. ` ` `  `# function for calculating max  ` `# possible result ` `def` `maxDP (n): ` `    ``res ``=` `list``() ` `    ``res.append(``0``) ` `    ``res.append(``1``) ` `     `  `    ``# Compute remaining values in  ` `    ``# bottom up manner. ` `    ``i ``=` `2` `    ``while` `i

## C#

 `// C# program for maximize result when ` `// we have choice to divide or consider ` `// as it is. ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// function for calculating max ` `    ``// possible result ` `    ``static` `int` `maxDP(``int` `n) ` `    ``{ ` `        ``int``[] res = ``new` `int``[n + 1]; ` `        ``res[0] = 0; ` `        ``res[1] = 1; ` ` `  `        ``// Compute remaining values in ` `        ``// bottom up manner. ` `        ``for` `(``int` `i = 2; i <= n; i++) ` `            ``res[i] = Math.Max(i, (res[i / 2] + res[i / 3] + res[i / 4] + res[i / 5])); ` ` `  `        ``return` `res[n]; ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 60; ` `        ``Console.WriteLine(``"MaxSum = "` `+ maxDP(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m `

/div>

## PHP

 ` `

Output :

```MaxSum = 106
```