Given an integer `n`

, find the maximum value that can be obtained using`n`

ones and only addition and multiplication operations. Note that, you can insert any number of valid bracket pairs.

Example:

Input: n = 12

Output: 81

Explanation: (1 + 1 + 1) * (1 + 1 + 1) * (1 + 1 + 1) * (1 + 1 + 1) = 81

## Approach: Dynamic Programming

Observe that, in order to find the answer for `n = 5`

, we need to consider the maximum answer obtainable from the answer of `2`

and `3`

, `1`

and `4`

. Thus, this problem has an **optimal substructure** property.

```
5
/ \
op(1, 4) op(2, 3)
/ \ / \
1 op(2, 2) op(1, 1) op(1, 2)
/ \ / \ / \
op(1, 1) op(1, 1) 1 1 1 op(1, 1)
/ \ / \ / \
1 1 1 1 1 1
```

Here, op(m, n) = max(answer for m + answer for n, answer for m * answer for n).

Clearly, from the tree above there are a lot of **overlapping sub-problems**. Owing to this and optimal substructure property, this problem is an ideal candidate for dynamic programming.

**Bottom-up approach:**

C++ code:

```
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long getMaximumValue(int n) {
vector<long long> dp(n + 1);
// dp[i] denotes maximum value that can be obtained from i ones
dp[0] = 0; // base case: with 0 ones answer is always 0
dp[1] = 1; // base case: with 1 one answer is 1
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i / 2; ++j) {
dp[i] = max({dp[i], dp[j] + dp[i - j], dp[j] * dp[i - j]});
}
}
return dp[n];
}
int main() {
cout << "n = " << 5 << " Maximum possible value " << getMaximumValue(5) << endl; // prints
cout << "n = " << 12 << " Maximum possible value " << getMaximumValue(12) << endl; // prints "81"
return 0;
}
```

Python code:

```
def getMaximumValue(n):
dp = [0] * (n + 1)
# dp[i] denotes maximum value that can be obtained from i ones
dp[0] = 0 # base case: with 0 ones answer is always 0
dp[1] = 1 # base case: with 1 one answer is 1
for i in range(2, n + 1):
for j in range(1, i // 2 + 1):
dp[i] = max(dp[i], dp[j] + dp[i - j], dp[j] * dp[i - j])
return dp[n]
if __name__ == ' __main__':
print('n =', 5, 'Maximum possible value', getMaximumValue(5))
print('n =', 12, 'Maximum possible value', getMaximumValue(12))
```

Time Complexity: `O(n)`

Space Complexity: `O(n)`

due to storing states in `dp`

array

**Exercise**: Code the top-down approach.

## Top comments (0)