Recursive Algorithm
-
Define a recursive function to find the maximum/minimum value of the expression starting from index=i and ending at index=j.
-
Iterate over the expression from k=i+1 to k=j-1 and increment k by 2 in each iteration so that E[k] is always an operator.
-
For every k, compute the value of the expression ELeft = E[i,k-1] and ERight = E[k+1,j].
-
Define a variable temp to store the value of the expression for the current parenthesization and a variable ans to store the optimal value of the expression.
-
If E[k] is +, then temp=ELeft+ERight else temp=ELeft*ERight. Compare temp with ans and update ans if required. If you need the maximum value of the expression and ans < temp, then update ans as ans = temp and vice versa for the minimum value.
By now, you must have understood the idea about the recursive approach. If not, then don’t worry. In the next section, we will see the implementation of the recursive approach along with time and space constraints which will improve your understanding of the problem.
C++ Implementation
/*C++ implementation of the problem to find the minimum and maximum value
of an expression with + and * */
#include <bits/stdc++.h>
using namespace std;
int evalExpressionMin(int i, int j, string str)
{
if (i > j)
return 0;
if (i == j)
{
return str[i] - '0';
}
int ans = INT_MAX;
for (int k = i + 1; k <= j - 1; k = k + 2)
{
int tempAns = 0, ELeft = 0, ERight = 0;
ELeft = evalExpressionMin(i, k - 1, str);
ERight = evalExpressionMin(k + 1, j, str);
if (str[k] == '+')
tempAns = ELeft + ERight;
if (str[k] == '*')
tempAns = ELeft * ERight;
ans = min(ans, tempAns);
}
return ans;
}
int evalExpressionMax(int i, int j, string str)
{
if (i > j)
return 0;
if (i == j)
return str[i] - '0';
int ans = INT_MIN;
for (int k = i + 1; k <= j - 1; k = k + 2)
{
int tempAns = 0, ELeft = 0, ERight = 0;
ELeft = evalExpressionMax(i, k - 1, str);
ERight = evalExpressionMax(k + 1, j, str);
if (str[k] == '+')
tempAns = ELeft + ERight;
if (str[k] == '*')
tempAns = ELeft * ERight;
ans = max(ans, tempAns);
}
return ans;
}
int main()
{
string S = "1+2*3+4*5";
int N = S.size();
int minn = evalExpressionMin(0, N - 1, S);
int maxx = evalExpressionMax(0, N - 1, S);
cout << "Minimum Value is " << minn << endl
<< "Maximum Value is " << maxx << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output
Minimum Value is 27
Maximum Value is 105
Time Complexity
The time complexity of the recursive approach is exponential. As, if you observe, the recurrence relation is -
E[i,j] = E[0]-’0’ if i==j
else
E[i,j] = min( E[i,k-1] operator E[k+1,j]) for all k=i+1 to k=j-1
Space Complexity
If we consider the recursion stack space, the space complexity will be O(n) because the maximum depth of the recursion will be n, and in each recursive call, we don't use any extra space. So, it is n*O(1) which is nothing but O(n).
Dynamic Programming Approach
The recursive solution solves many subproblems repeatedly, and as a result, it is not time efficient. So, if we want to optimize the solution, one way is to avoid the repetitive computation of the same subproblem and improve the time complexity. How do we do that?
We will store the result of every subproblem once it is solved, and afterwards, if we encounter the same subproblem again, we will reuse the stored result and won't compute it again.
We will consider the bottom-up approach, which implies we will start by solving smaller subproblems and use them to compute larger subproblems.
Let’s see the code implementation and the time and space complexity analysis in the next section.
C++ Implementation
/*C++ implementation of the problem to find the minimum and maximum value
of an expression with + and * */
#include <bits/stdc++.h>
using namespace std;
// function to check if a given character is an operator or not
bool isOperator(char op)
{
return (op == '+' || op == '*');
}
void minMaxValExpression(string E)
{
string temp = "";
vector<int> numbers; // stores the numbers from the exression
vector<char> operators; // stores the operators from the exression
for (int i = 0; i < E.length(); i++)
{
if (isOperator(E[i]))
{
operators.push_back(E[i]);
numbers.push_back(atoi(temp.c_str()));
temp = "";
}
else
{
temp += E[i];
}
}
numbers.push_back(atoi(temp.c_str()));
int length = numbers.size();
int minValExp[length][length];
int maxValExp[length][length];
// initializing the 2d arrays minValExp and maxValExp
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
minValExp[i][j] = INT_MAX;
maxValExp[i][j] = 0;
// for an expression of length 1 i.e. i=j
if (i == j)
minValExp[i][j] = maxValExp[i][j] = numbers[i];
}
}
for (int L = 2; L <= length; L++)
{
for (int i = 0; i < length - L + 1; i++)
{
int j = i + L - 1;
for (int k = i; k < j; k++)
{
int tempMin = 0, tempMax = 0;
if (operators[k] == '*')
{
tempMin = minValExp[i][k] * minValExp[k + 1][j];
tempMax = maxValExp[i][k] * maxValExp[k + 1][j];
}
else if (operators[k] == '+')
{
tempMin = minValExp[i][k] + minValExp[k + 1][j];
tempMax = maxValExp[i][k] + maxValExp[k + 1][j];
}
if (tempMin < minValExp[i][j])
minValExp[i][j] = tempMin;
if (tempMax > maxValExp[i][j])
maxValExp[i][j] = tempMax;
}
}
}
cout << "Minimum value is " << minValExp[0][length - 1]
<< "\nMaximum value is " << maxValExp[0][length - 1];
}
int main()
{
string E = "1+2*3+4*5";
minMaxValExpression(E);
return 0;
}
You can also try this code with Online C++ Compiler
Output
Minimum Value of the expression is 27
Maximum Value of the expression is 105
Time Complexity
O(n^3), as we have three nested loops in the function.
Space Complexity
O(n^2), since we are using a 2D matrix to store the values of all the subproblems.
Frequently Asked Questions
-
Is recursion important for coding interviews?
Recursion is the foundation of logic, local variables, the call-stack, and much more. It utilises a logic-driven intuitive cognitive approach. One of the most prevalent reasons individuals want to comprehend recursion is frequently asked during interviews.
-
What is Dynamic Programming?
Dynamic programming is an optimization for recursion. We have to calculate the same calculation repeatedly, making a stack going in-depth, but using DP, we can overcome this problem.
Key Takeaways
In this article, we learnt to solve the problem to find the minimum and maximum value of an expression with + and *. We started with a very intuitive brute force approach, and we obtained a very beautiful recursive solution. Then based upon our understanding, we observed the brute force solution's inefficiency, so we optimized it through memoization.
Check out this problem - Maximum Product Subarray
You must have got an idea about problem-solving in this blog. But without practice, your learning is incomplete. Keep practising and keep challenging yourself with new problems on Coding Ninjas Studio.
We also have guided paths especially curated for you, which is your one-stop solution for any topic you have always wanted to learn most intuitively and easily.
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!
568+ registered 
