我想到的算法存在以下问题（上carrercup找到）：

I am thinking about the algorithm for the following problem (found on carrercup):

由于有N个顶点和n条边的多边形。有一个int数（可以是负的）上的每个顶点和在每个边沿操作（*，+）。每一次，我们从多角移除缘部E，合并两个顶点由边缘（V1，V2）连接到一个新的顶点与值：V 1运算（E）的V 2。最后一种情况下将两个顶点与两个边缘，其结果是更大的。 返回最大结果值可以从给定的多边形来得到。

Given a polygon with N vertexes and N edges. There is an int number(could be negative) on every vertex and an operation in set(*,+) on every edge. Every time, we remove an edge E from the polygon, merge the two vertexes linked by the edge(V1,V2) to a new vertex with value: V1 op(E) V2. The last case would be two vertexes with two edges, the result is the bigger one. Return the max result value can be gotten from a given polygon.

我想我们可以只使用贪婪的方法。即为多边形，其中k边缘找到一对（P，Q）倒塌时产生的最大数量：（P，Q）=最大（{I操作约：I，J - 相邻边缘）

I think we can use just greedy approach. I.e. for polygon with k edges find a pair (p, q) which produces the maximum number when collapsing: (p ,q) = max ({i operation j : i, j - adjacent edges)

然后，只需拨打多边形递归： 1.设函数CollapseMaxPair（P（K）） - 获取多边形k条边，并返回'崩溃'的多边形与K-1的边缘 2.然后我们的递归：

Then just call a recursion on polygons: 1. Let function CollapseMaxPair( P(k) ) - gets polygon with k edges and returns 'collapsed' polygon with k-1 edges 2. Then our recursion:

 P = P(N);
 Releat until two edges left
     P =  CollapseMaxPair( P )
 maxvalue = max ( two remained values)

你怎么看？

推荐答案

我在这里回答了这个问题：Google专访：找到一个多边形的最高金额，并有人向我指出，这一问题是这其中的一个副本。由于没有人回答了这个问题尚未完全，我决定在这里添加这个答案也是如此。

I have answered this question here: Google Interview : Find the maximum sum of a polygon and it was pointed out to me that that question is a duplicate of this one. Since no one has answered this question fully yet, I have decided to add this answer here as well.

正如你已经确定（标签）正确的，这确实是非常相似的矩阵乘法问题（在什么样的顺序我为了迅速做乘法矩阵）。

As you have identified (tagged) correctly, this indeed is very similar to the matrix multiplication problem (in what order do I multiply matrixes in order to do it quickly).

这可以多项式利用动态算法来解决。

This can be solved polynomially using a dynamic algorithm.

我要，而不是解决类似的，比较经典的（和相同的）问题，给出的数字，加法和乘法公式，有什么办法圆括号它给出了最大值，例如 6 + 1 * 2 变成（6 + 1）* 2 这是比 6 +（1 * 2）。

I'm going to instead solve a similar, more classic (and identical) problem, given a formula with numbers, addition and multiplications, what way of parenthesizing it gives the maximal value, for example 6+1 * 2 becomes (6+1)*2 which is more than 6+(1*2).

让我们表示我们的输入 A1至实数和O（1），...... O（N-1）或者 * 或 + 。我们的方法将工作方式如下，我们将观察子问题F（I，J），从而重新presents最大公式（parenthasizing后）A1，... AJ。我们将创造这样子问题一个表，并观察F（1，N）正是我们所期待的结果。

Let us denote our input a1 to an real numbers and o(1),...o(n-1) either * or +. Our approach will work as follows, we will observe the subproblem F(i,j) which represents the maximal formula (after parenthasizing) for a1,...aj. We will create a table of such subproblems and observe that F(1,n) is exactly the result we were looking for.

定义

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

这个经过所有可能的选择。正确性TProof通过感应的大小为n =吉做，是pretty的小事。

This goes through all possible options. TProof of correctness is done by induction on the size n=j-i and is pretty trivial.

让我们通过运行时分析：

如果我们不动态地保存值较小的子这个运行pretty的慢，但是我们可以让这个算法进行比较快的为O（n ^ 3）

If we do not save the values dynamically for smaller subproblems this runs pretty slow, however we can make this algorithm perform relatively fast in O(n^3)

我们创建一个* N表T在该小区的指数I，J包含F（I，J）灌装F（I，I）和F（I，J）对于j小于我是为O完成（ 1）针对每个小区，因为我们可以直接计算出这些值，然后我们去斜，并填写F（I + 1，I + 1）（我们可以很快做到，因为我们已经知道的递推公式所有的previous值），我们重复这个n次n个对角线（表中的真正所有的对角线）和填充每个单元需要（为O（n）），因为每个单元有O（n）的细胞，我们填写每个对角线的为O（n ^ 2 ）这意味着我们填写的所有表格中为O（n ^ 3）。填充表之后，我们明明知道F（1，N），这是解决你的问题。

We create a n*n table T in which the cell at index i,j contains F(i,j) filling F(i,i) and F(i,j) for j smaller than i is done in O(1) for each cell since we can calculate these values directly, then we go diagonally and fill F(i+1,i+1) (which we can do quickly since we already know all the previous values in the recursive formula), we repeat this n times for n diagonals (all the diagonals in the table really) and filling each cell takes (O(n)), since each cell has O(n) cells we fill each diagonals in O(n^2) meaning we fill all the table in O(n^3). After filling the table we obviously know F(1,n) which is the solution to your problem.

现在回到你的问题

如果你翻译的多边形进 N 配方不同（一个是开始在每个顶点），然后运行该算法就可以了公式的值，你得到你想要完全值

If you translate the polygon into n different formulas (one for starting at each vertex) and run the algorithm for formula values on it, you get exactly the value you want.