谷歌面试：找一个多边形的最大总和 [英] Google Interview : Find the maximum sum of a polygon

问题描述

考虑到与 N 顶点和 N 边的多边形。有一个int数（可以是负的）上的每个顶点和集（*，+）在每个边沿的操作。每一次，我们从多边形中删除边缘E，合并两个顶点的边缘（V1，V2）来一个新的顶点与价值链接： V1 OP（E）V2 。最后一种情况下将两个顶点与两个边缘，其结果是更大的一个

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.

在过去的情况下，我们可能并不需要两个合并为其他数量可能是负的，所以在这种情况下，我们将只返回数量较多。

For the last case we might not need two merge as the other number could be negative, so in that case we would just return the larger number.

我如何接近这个问题：

 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 .

我可以做的更好，然后呢？

Can i do better then this ?

推荐答案

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

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.

这篇关于谷歌面试：找一个多边形的最大总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！