## DEV Community

Ayan Banerjee

Posted on • Originally published at notescs.gitlab.io

# Maximum Value of Equation of Ones with Addition and Multiplication Operations - An Interview Problem

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.