# Maximum Value of Equation of Ones with Addition and Multiplication Operations

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 ^ 2)$
Space Complexity: $O(n)$ due to storing states in dp array

Exercise: Code the top-down approach.