1

问题出现在 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];
}

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

4

1 回答 1

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 解决了这个问题。

于 2019-05-18T16:29:30.607 回答