Algorithmic Toolbox : Maximize Arithmetic expression using parentheses? Failed Test Case #5/19

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.

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.

The maximum and minimum functions

long long maximum(long long a,long long b,long long c,long long d)
{
    int a1 = a>b?a:b;
    int a2 = c>d?c:d;
    return a1>a2?a1:a2;
}

long long minimum(long long a,long long b,long long c,long long d)
{
    int a1 = a<b?a:b;
    int a2 = c<d?c:d;
    return a1<a2?a1:a2;
}

The eval function

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);
  }
}

The algorithm implementation

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<n;i++)
  {
      max[i] = (long long*)malloc(n*sizeof(long long));
      min[i] = (long long*)malloc(n*sizeof(long long));
  }
  for(i=0;i<n;i++){
    max[i][i] = str[i*2] - '0';
    min[i][i] = str[i*2] - '0';
  }
  for(i=1;i<n;i++)
    for(j=0;i+j<n;j++)
    {
        max[j][i+j] = LLONG_MIN;
        min[j][i+j] = LLONG_MAX;
        for(k=j;k<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>max[j][i+j]) max[j][i+j] = a1;
            if(b1<min[j][i+j]) min[j][i+j] = b1;
        }
    }
  return max[0][n-1];
}

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.

I got the problem. It was integer overflow. I actually defined a1 and a2 as int inside the maximum and minimum function.

long long maximum(long long a,long long b,long long c,long long d)
{
    long long a1 = a>b?a:b;
    long long a2 = c>d?c:d;
    return a1>a2?a1:a2;
}

long long minimum(long long a,long long b,long long c,long long d)
{
    long long a1 = a<b?a:b;
    long long a2 = c<d?c:d;
    return a1<a2?a1:a2;
}

Changing it into long long solved the problem.