CareerCup

cin >> s;
n = strlen(s);

// initialise dp array with all zeros

for(i = 0; i < n; i+=2)
dp[i][i] = s[i];

for(l = 2; l < n; l+=2)
{
for(i = 0; i < n; i+=2)
{
j = i + l;
for(k = i ; k < j; k+=2)
{
dp[i][j] = max(dp[i][j], apply_operator(dp[i][k], dp[k+2][j], s[k+1] )) // here s[k+1] would be be operator
}
}
}
print dp[0][n-1]

i think DP will certainly help here but how dont able to figure it out so please any one post the logic :)

Similar to chain matrix multiplication.

V(a, op, b)
	if(op == '+')
		return(a+b)
	if(op == '-')
		return(a-b)
	if(op == '*')
		return(a*b)
	if(op == '/')
		return(a/b)	

MVE(i, j)
	return max{V(MVE(i, j-2), a[j-1], a[j]), V(MVE(i+2, j), a[i+1], a[i])}

Use recursion; algorithm

;assumption - every operand is single digit, code can be expanded easily to handle operands >9
int toVal(string); converts a string number into integer/double
int EvalExp(string); evaluates the expression from left to right without any precedence
double MaxEvalExp(string expression, int start, int end, bool isFull) {
   char ch; int operand;
   if (start==end) return toVal(expression);
   for (int i=0; i<=(end-start); i++) {
       ch = expression[i];
       switch (ch) {
           case '+': operand = EvalExp(expression.substring(start,(i-start)+1));
                           result = operand + MaxEvalExp(expression, i+1, end, false);
                           if (isFull) && (result>maxValue) maxValue = result;

           case '-':  operand = EvalExp(expression.substring(start,(i-start)+1));
                           result = operand - MaxEvalExp(expression, i+1, end, false);
                           if (isFull) && (result>maxValue) maxValue = result;

           case '*':  operand = EvalExp(expression.substring(start,(i-start)+1));
                           result = operand * MaxEvalExp(expression, i+1, end, false);
                           if (isFull) && (result>maxValue) maxValue = result;
       
           case '/':  operand = EvalExp(expression.substring(start,(i-start)+1));
                           result = operand / MaxEvalExp(expression, i+1, end, false);
                           if (isFull) && (result>maxValue) maxValue = result;
       }
   }
}

int main() {
  string expression;
  cin >> expression;
  MaxEvalExp(expression, 0, expression.length-1, true);
  cout << "Maximum Value: " << maxValue;
  return 0;
}

int EvalExp(int lVal, int rVal, char op){
	switch(op){
		case'+':
			return (lVal+rVal);
		case'-':
			return (lVal-rVal);
		case'*':
			return (lVal*rVal);
		case'/':
			return (lVal/rVal);
	}
}

int EvalMaxHelper(string str, int start, int end){
	int maxVal;
	int lVal,rVal;
	int val;
	const int NEG_INFINITY=-99999;
	stringstream ss;
	maxVal=NEG_INFINITY;
	for(int i=start; i<end; i++){
		if(str[i]=='+' || str[i]=='-' || str[i]=='*' || str[i]=='/' ){
			lVal=EvalMaxHelper(str,start,i-1);
			rVal=EvalMaxHelper(str,i+1,end);
			val=EvalExp(lVal,rVal,str[i]);
			if (val>maxVal)
				maxVal=val;
		}
	}

	if (maxVal==NEG_INFINITY){
		ss<<str.substr(start,(end-start+1));
		ss>>maxVal;
	}

	return maxVal;
}

void EvalMax(){
	string str="2*3+5-3";
	cout << "Maximum value: " << EvalMaxHelper(str,0,str.length()-1) << endl;
}