算法工具箱：使用括号最大化算术表达式？失败的测试用例 #5/19

Question

问题出现在 Coursera 算法工具箱课程的第 6 周。题目是求一个只有+,-,*组成的算术表达式的最大值

我编写了一个解决方案，运行它带有测试用例，并且还对在线提供的其他解决方案进行了压力测试。我的代码似乎无处不在运行。但是每当我尝试提交它时，第 5 个测试用例都失败了。一开始以为是long long值溢出，所以提交了double数据类型的方案。问题依旧。

最大值和最小值函数

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

评估函数

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

算法实现

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

有没有人遇到过类似的问题？如果可能，请建议使用代码的测试用例将失败。这将非常有帮助。提前致谢。

Answer 1

我明白了。这是整数溢出。我实际上在最大和最小函数中将a1和a2定义为int。

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

改成long long就解决了。

算法工具箱：使用括号最大化算术表达式？失败的测试用例 #5/19

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

c

algorithm

coursera-api