DEV Community

Ayan Banerjee
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 usingn 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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(n)
Space Complexity: O(n) due to storing states in dp array

Exercise: Code the top-down approach.

Latest comments (0)