Last Updated on April 8, 2022 by Ria Pathak
Concepts Used
Strings
Difficulty Level
Hard
Problem Statement (Simplified):
Find the maximum answer by evaluating the given string and putting a bracket anywhere in the string.
See original problem statement here
Test Case
Input:
2
3+4*5+6
3*5+6*7+2
Output:
47
233
Explanation:
Case-1:
We can put brackets at last operator making equation as 3+4*(5+6) => 3+4*11 => 47.
Case-2:
We can put bracket at 2nd operator making equation as 3*(5+6)*7+2 => 3*11*7+2 => 33*7+2 => 231+2 => 233.Solving Approach :
Bruteforce Approach:
1) We can place brackets at all possible positions and check the value of all possible cases and then we can find the maximum value out of them, thus we print the maximum value.
2) Evaluating string of sizeLtakesO(N)time, where checking all possibilities takeO(M)times where M is the number of operators i.e.*or+in whole string. So this approach takes totalO(M\times N)time complexity. The above approach takes a long time to evaluate strings of larger sizes. So we search for an optimized approach that can solve this problem in a shorter time.
Efficient Approach:
1) An easy analysis shows that the brackets must be placed adjacent to
*sign since they won’t have any effect next to a+sign.
2) We need to store the indexes of all the*in the string and iterate over all possible pairs. One thing to keep in mind is the maximum case may be one in which the brackets start at the 0th index or the one in which it ends at the last index.
Example
- Lets assume given equation is
3*5+6*7+2.- As discussed in
Step-1, the equation will be maximized if we put brackets adjacent to a multiplication operator. So we get two possibilities here, that is,3*(5+6)*7+2and3*5+6*(7+2).- On evaluating above equations, equations yield
233and69respectively, where the first equation yields the maximum value. So it is our final answer.
Solutions
#include <stdio.h>
long long a[5002],b[5002],c[5002],c1[5002];
long long fun(long long l,long long r)
{
if(l==r)
return a[l];
long long sum=0,i;
for(i=l;i<=r;i++)
b[i]=a[i];
for(i=l;i<r;i++)
{
if(c[i]==1)
{
sum+=b[i];
}
else
{
b[i+1]=b[i]*b[i+1];
}
}
sum+=b[r];
return sum;
}
long long fun2(long long l,long long r)
{
if(l==r)
return b[l];
long long sum=0,i;
for(i=l;i<r;i++)
{
if(c1[i]==1)
{
sum+=b[i];
}
else
{
b[i+1]=b[i]*b[i+1];
}
}
sum+=b[r];
return sum;
}
int main()
{
int test;
scanf("%d",&test);
while(test--){
char str[5003];
scanf ("%s",&str);
long long i=0,j,mul[16],ctr=0,len=0,sum=0,max=-1,k,k1;
mul[0]=-1;
ctr++;
while (str[i]!='\0')
{
if(str[i]=='+')
c[i/2]=1;
else if (str[i]=='*')
{
mul[ctr]=i/2;
ctr++;
c[i/2]=2;
}
else
{
a[i/2]=str[i]-48;
sum+=a[i/2];
}
i++;
len++;
}
mul[ctr]=len/2;
ctr++;
for(i=0;i<=len/2;i++)
{
}
if(ctr==0)
{
printf ("%lld\n",sum);
return 0;
}
for(i=0;i<ctr;i++)
{
for(j=i+1;j<ctr;j++)
{
long long temp2=fun(mul[i]+1,mul[j]);
k=0;
if(mul[i]!=-1)
{
for(k=0;k<mul[i]+1;k++)
{
b[k]=a[k];
c1[k]=c[k];
}
}
b[k]=temp2;
c1[k]=2;
k++;
for(k1=mul[j]+1;k1<=len/2;k1++)
{
b[k]=a[k1];
c1[k]=c[k1];
k++;
}
long long tt=fun2(0,k-1);
if(tt>max)
max=tt;
}
}
printf ("%lld\n",max);
}return 0;
}
#include <stdio.h>
long long a[5002],b[5002],c[5002],c1[5002];
long long fun(long long l,long long r)
{
if(l==r)
return a[l];
long long sum=0,i;
for(i=l;i<=r;i++)
b[i]=a[i];
for(i=l;i<r;i++)
{
if(c[i]==1)
{
sum+=b[i];
}
else
{
b[i+1]=b[i]*b[i+1];
}
}
sum+=b[r];
return sum;
}
long long fun2(long long l,long long r)
{
if(l==r)
return b[l];
long long sum=0,i;
for(i=l;i<r;i++)
{
if(c1[i]==1)
{
sum+=b[i];
}
else
{
b[i+1]=b[i]*b[i+1];
}
}
sum+=b[r];
return sum;
}
int main()
{
int test;
scanf("%d",&test);
while(test--){
char str[5003];
scanf ("%s",&str);
long long i=0,j,mul[16],ctr=0,len=0,sum=0,max=-1,k,k1;
mul[0]=-1;
ctr++;
while (str[i]!='\0')
{
if(str[i]=='+')
c[i/2]=1;
else if (str[i]=='*')
{
mul[ctr]=i/2;
ctr++;
c[i/2]=2;
}
else
{
a[i/2]=str[i]-48;
sum+=a[i/2];
}
i++;
len++;
}
mul[ctr]=len/2;
ctr++;
for(i=0;i<=len/2;i++)
{
}
if(ctr==0)
{
printf ("%lld\n",sum);
return 0;
}
for(i=0;i<ctr;i++)
{
for(j=i+1;j<ctr;j++)
{
long long temp2=fun(mul[i]+1,mul[j]);
k=0;
if(mul[i]!=-1)
{
for(k=0;k<mul[i]+1;k++)
{
b[k]=a[k];
c1[k]=c[k];
}
}
b[k]=temp2;
c1[k]=2;
k++;
for(k1=mul[j]+1;k1<=len/2;k1++)
{
b[k]=a[k1];
c1[k]=c[k1];
k++;
}
long long tt=fun2(0,k-1);
if(tt>max)
max=tt;
}
}
printf ("%lld\n",max);
}return 0;
}
import java.util.*;
import java.io.*;
import java.math.*;
class Main {
static long a[] = new long[6000];
static long b[] = new long[6000];
static long xx,yy,x,y,k,ans;
static int i,j,m,n;
static String s,t;
static void solve(int l, int r)
{
x = 0; y = a[l];
for (int i = l; i < r; i++)
if (b[i] == 1)
{
x += y; y = a[i+1];
}
else
y *= a[i+1];
}
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while(test!=0){
s = sc.next();
t = "1*";
t = t.concat(s);
t = t.concat("*1");
s = t;
n = s.length();
m = n/2;
for (i = 0; i < n; i+=2)
a[i/2] = (int)s.charAt(i) - (int)'0';
for (i = 1; i < n; i+=2)
if (s.charAt(i) == '+')
b[i/2] = 1;
else
b[i/2] = 2;
long max1 = 0;
for (i = 0; i < m; i++)
for (j = i+1; j < m; j++)
if (b[i] == 2 && b[j] == 2)
{
solve(0,i);
xx = x; yy = y;
solve(i+1,j);
yy *= x + y;
long xxx = a[j];
a[j] = yy;
solve(j,m);
max1 = Math.max(max1, xx+x+y);
a[j] = xxx;
}
System.out.println(max1);
test--;
}
}
}
[forminator_quiz id="727"]
Space complexity of this approach would be O(N).
This article tried to discuss Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.