谷歌面试题：寻找多边形的最大和

Question

给定一个有N个顶点和N条边的多边形。每个顶点上都有一个整数（可以是负数），每条边上都有一个操作符（在集合*和+中）。每次从多边形中移除一条边E，将由该边连接的两个顶点（V1，V2）合并成一个新顶点，其值为：V1 op(E) V2。最后一种情况是只剩下两个带有两条边的顶点，结果是两者中的大值。

返回给定多边形所能获得的最大结果值。

对于最后一种情况，我们可能不需要合并两个顶点，因为另一个数字可能是负数，在这种情况下，我们将只返回更大的数字。

我如何解决这个问题：

 p[i,j] denotes the maximum value we can obtain by merging nodes from labelled i to j.
 p[i,i] = v[i] -- base case
 p[i,j] = p[i,k] operator in between p[k+1,j] , for k between i to j-1.
and then p[0,n] will be my answer.
Second point , i will have to start from all the vertices and do the same as above as this will be cyclic n vertices n edges.
The time complexity for this is n^3 *n i.e n^4 .

我能做得比这更好吗？

- Peter

---

我不知道为什么一些相同的人每天都投票反对我的问题。你们有什么个人恩怨吗，是我有时没有接受你们的答案吗？这个问题有什么太局限或离题的地方吗？这是一个算法问题，我已经写出了我的方法，我正在寻找更优化的方法（如果存在），我非常坦率地说这是一个Google面试问题，那些投票关闭的人还想要什么呢？ - Peter

也许有些人认为这会破坏未来候选人的面试？我希望人们能够给出否决的原因等。 - djna

多边形的顶点上有权重，对边进行操作的算法。 - AndyG

那里没有解决方案，仍然是空着的。 - Peter

我已经为你的问题添加了一个解决方案，还有更有效的解决方案，但它们要复杂得多，让我知道你的想法。 - Benjamin Gruenbaum

Answer 1

正如你正确地识别（标记）的那样，这确实非常类似于矩阵乘法问题（按什么顺序乘矩阵才能快速完成）。

这可以用动态规划算法多项式地解决。

我将解决一个类似的、更经典（并且相同）的问题，即给定一个带有数字、加法和乘法的公式，哪种括号方式可以给出最大值，例如6+1 * 2变为(6+1)*2比6+(1*2)更大。

让我们将输入a1到an表示为实数，将o(1)到o(n-1)表示为*或+。我们的方法如下：我们将观察子问题F(i,j)，它表示a1,...aj的最大公式（经过括号化）。我们将创建这些子问题的表，并观察到F(1,n)正是我们要寻找的结果。

定义

F(i,j)

 - If i>j return 0 //no sub-formula of negative length
 - If i=j return ai // the maximal formula for one number is the number
 - If i<j return the maximal value for all m between i (including) and j (not included) of:
     F(i,m) (o(m)) F(m+1,j) //check all places for possible parenthasis insertion

这将穷举所有可能的选项。对于大小为n=j-i的情况，正确性的证明通过归纳完成，这是非常显然的。

现在来分析运行时间：

如果我们不为较小的子问题动态保存值，则运行速度相当慢，但我们可以使此算法以O(n^3)的速度执行得相对快速。我们创建一个n * n的表T，在其中，索引i，j处的单元格包含F(i,j)，填充F(i,i)和F(i,j)（对于小于i的j）每个单元格的时间复杂度都是O(1)，因为我们可以直接计算这些值，然后我们沿对角线前进并填充F(i+1,i+1)（由于我们已经知道递归公式中的所有先前值，因此我们可以快速完成），我们对n个对角线（实际上是表中的所有对角线）重复此操作n次。由于每个单元格具有O(n)个单元格，因此我们用O(n^2)的时间填充每个对角线，这意味着我们用O(n^3)的时间填充了整个表。填充表后，我们显然知道F(1,n)，这是您问题的解答。

现在回到您的问题：

如果您将多边形转换为n个不同的公式（从每个顶点开始），并在其上运行该算法，则可以获得所需的确切值。

- Benjamin Gruenbaum

Answer 2

我认为你可以减少暴力搜索的需求。例如：如果有一条链

x + y + z

你可以用一个值为总和的单个顶点来替换它，这是最好的选择。当你处理正整数时，需要在加法之后进行乘法运算。因此，如果全部都是正数，则简单地减少所有+链，然后进行乘法。

那么就只剩下有负数的情况了。对于单个负数，策略似乎很明显，对于两个负数，有几种情况（记住- x -是正数），对于超过2个负数，似乎会变得棘手 :-)

- djna