这是我之前被问到的一个面试问题：
假设给你一个表达式 E= x1 y1 x2 y2....yn-1 xn。
其中 Xi 属于自然数，Yi 属于 { +,*}。
你需要加括号以使 E 的值最大化？
我能够想到动态规划的方向，并将其与矩阵链乘法问题联系起来，但在推导出准确的递归关系时卡住了。
此外，后续问题只会让情况变得更加复杂：
现在将 Yi 更改为 { +,-,*,/}，如何最大化 E？现在在该集合中添加%运算符...那么如何最大化 E？
关于如何处理并构建这个问题的解决方案的说明将是非常好的。
F(i,j) = maximum number that can be computed using Xi ... Xj
F(i,i) = Xi
递归情况是用于在括号中包含两个子表达式之间的操作：
F(i,j) = for k = i,j-1, maximize
F(i,k) Yk F(k+1, j)
我认为贪心地最大化数字应该可行，因为对于正数的乘法和加法，我们希望两个操作数尽可能大。
如果我们允许除法，那么我们将希望第二个操作数尽可能小以最大化结果。在这种情况下，除了计算 F 之外，您还需要计算类似的 G，以最小化区间内的值。
如果我们允许减法，则需要考虑正数与负数的问题。如果您跟踪最大正数、最小正数、最大负数和最小负数，我认为您应该能够获得所需的任何值。也许有一种需要更少计算的替代方法。
我没有停下来思考 % 的影响。首先，它如何处理 / 的非整数结果？
通过动态规划，可以计算在假定在Xi和Xj之间加上外层括号的情况下所能得到的最大表达式。你的动态规划递归需要对所有可能插入一对相邻括号集合的方式进行迭代，在所有子情况的最大可能值中计算出最大可能值。如果有n个项，则这将天真地给出一个O(n^3)时间复杂度的算法。
当允许除法和减法时，事情变得更加复杂，与另一个答案所建议的相反。例如，如果要最大化，而且有除法，则如果最大值为正，则要最大化分子，并使分母尽量接近1，同时保持正数；或者如果最小值为负，则要最小化分子，并使分母尽量接近-1，同时保持负数。如果分子和分母的符号不能匹配，则要最小化分子的大小并最大化分母的大小。最后一种情况不难，但前两种情况似乎非常棘手。如果你被允许使用所有4种算术运算符，那么你如何能够在保持符号的情况下尽可能接近1或-1呢？这甚至可能是一个NP难问题，特别是如果还包括取模运算。