title: Algorithmic Toolbox : Maximize Arithmetic expression using parentheses? Failed Test Case #5/19
body: <p>The problem was in week 6 of algorithmic toolbox course on Coursera. The problem is to find out the maximum value of an arithmetic expression consisting of + , - and * only.</p>
  
  <p>I coded a solution, have run it with test cases and also incurred a stress test with other solutions available online. Everywhere my code seems to run fine. But whenever I am trying to submit it is failing the 5th test case. First I thought it was due to value overflow in long long, so submitted the solution with double data type. Still the problem remains.</p>
  
  <p>The maximum and minimum functions</p>
  
  <pre class="lang-c prettyprint-override"><code>long long maximum(long long a,long long b,long long c,long long d)
  {
      int a1 = a&gt;b?a:b;
      int a2 = c&gt;d?c:d;
      return a1&gt;a2?a1:a2;
  }
  
  long long minimum(long long a,long long b,long long c,long long d)
  {
      int a1 = a&lt;b?a:b;
      int a2 = c&lt;d?c:d;
      return a1&lt;a2?a1:a2;
  }
  </code></pre>
  
  <p>The eval function</p>
  
  <pre class="lang-c prettyprint-override"><code>long long eval(long long a, long long b, char op) {
    if (op == '*') {
      return a * b;
    } else if (op == '+') {
      return a + b;
    } else if (op == '-') {
      return a - b;
    } else {
      assert(0);
    }
  }
  </code></pre>
  
  <p>The algorithm implementation</p>
  
  <pre class="lang-c prettyprint-override"><code>long long get_maximum_value(char *str) {
    int len = strlen(str);
    int n = (len+1)/2,i,j,k;
    long long a,b,c,d,a1,b1;
    long long **max = (long long **)malloc(n*sizeof(long long*));
    long long **min = (long long **)malloc(n*sizeof(long long*));
    for(i=0;i&lt;n;i++)
    {
        max[i] = (long long*)malloc(n*sizeof(long long));
        min[i] = (long long*)malloc(n*sizeof(long long));
    }
    for(i=0;i&lt;n;i++){
      max[i][i] = str[i*2] - '0';
      min[i][i] = str[i*2] - '0';
    }
    for(i=1;i&lt;n;i++)
      for(j=0;i+j&lt;n;j++)
      {
          max[j][i+j] = LLONG_MIN;
          min[j][i+j] = LLONG_MAX;
          for(k=j;k&lt;i+j;k++)
          {
              a = eval(max[j][k],max[k+1][i+j],str[2*k+1]);
              b = eval(max[j][k],min[k+1][i+j],str[2*k+1]);
              c = eval(min[j][k],max[k+1][i+j],str[2*k+1]);
              d = eval(min[j][k],min[k+1][i+j],str[2*k+1]);
              a1 = maximum(a,b,c,d);
              b1 = minimum(a,b,c,d);
              if(a1&gt;max[j][i+j]) max[j][i+j] = a1;
              if(b1&lt;min[j][i+j]) min[j][i+j] = b1;
          }
      }
    return max[0][n-1];
  }
  </code></pre>
  
  <p>Have anyone faced a similar problem? Please if possible suggest a test case for with the code will fail. It will be very helpful.
  Thanks in advance.</p>