➤ Problem Link : LISA
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll dp[105][105];
ll small[105][105];
ll op(ll x,ll y,char op)
{
switch(op)
{
case '*':
return x*y;
case '+':
return x+y;
default :
return -1;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin>>k;
while(k--)
{
string s;
cin>>s;
memset(dp,0,sizeof(dp));
memset(small,0,sizeof(small));
for(int i=0;i<s.length();i+=2)
{
dp[i][i]=s[i]-'0';
small[i][i]=s[i]-'0';
}
int i,j;
for(int k=2;k<s.length();k+=2)
{
for(i=0,j=k;i<s.length(),j<s.length();i+=2,j+=2)
{
dp[i][j]=-1;
small[i][j]=INT_MAX;
for(int ind=i;ind<=j-2;ind+=2)
{
dp[i][j]=max(dp[i][j],op(dp[i][ind],dp[ind+2][j],s[ind+1]));
small[i][j]=min(small[i][j],op(small[i][ind],small[ind+2][j],s[ind+1]));
}
}
}
cout<<dp[0][s.length()-1]<<" "<<small[0][s.length()-1]<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.