谷歌采访：找到多边形的最大和[关闭]

给定一个多边形N顶点和N边缘。每个顶点上都有一个 int 数（可以是负数）和 set 中的一个操作(*,+)在每个边缘。每次，我们从多边形中删除一条边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 .

我可以做得更好吗？

正如您已经正确识别（标记）的那样，这确实与矩阵乘法问题非常相似（我以什么顺序乘以矩阵以便快速完成）。

这可以使用动态算法通过多项式求解。

我将解决一个类似的、更经典（且相同）的问题，给定一个包含数字、加法和乘法的公式，例如，用括号括起来的方式会给出最大值6+1 * 2变成(6+1)*2这超过了6+(1*2).

让我们表示我们的输入a1 to an实数和 o(1),...o(n-1) 之一* or +。我们的方法将按如下方式工作，我们将观察子问题 F(i,j)，它表示 a1,...aj 的最大公式（括号化后）。我们将创建一个此类子问题的表，并观察 F(1,n) 正是我们正在寻找的结果。

Define

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) 个单元格，我们用 O(n^2) 填充每个对角线，这意味着我们填充所有O(n^3) 中的表。填写表格后，我们显然知道 F(1,n) 这是您问题的解决方案。

现在回到你的问题

如果将多边形转换为n不同的公式（从每个顶点开始）并对其运行公式值的算法，您将得到您想要的值。