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

问题描述

给定一个多边形，具有 N 顶点和 N 边。每个顶点都有一个int数字（可以是负数），每个边上都有一个集合（*，+）中的操作。每次，我们从多边形中删除一个边E，将由边缘（V1，V2）链接的两个顶点合并到一个新的顶点，值为： V1 op（E）V2 。最后一种情况将是两个具有两个边的顶点，结果是较大的一个。

返回从给定的多边形可以得到的最大结果值。

对于最后一种情况，我们可能不需要两个合并，因为其他数字可能是负数，所以在这种情况下，我们只会返回较大的数字。

我如何处理问题：

  p [i，j]表示我们可以获得的最大值通过将节点从标记的i合并到j。 
p [i，i] = v [i]  - 基本情况
p [i，j] = p [i，k]在p [k + 1，j]之间的运算符，到j-1。 
然后p [0，n]将是我的答案。 
第二点，我将不得不从所有的顶点开始，并做同样的，因为这将是循环n个顶点n个边。 
这个时间复杂度是n ^ 3 * n，即n ^ 4。 
  

我可以做得更好吗？

解决方案

正如你已经正确识别（标记的），这确实非常类似于矩阵乘法问题（为了快速地执行矩阵乘法，我以多少顺序排列）。

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

我要解决一个类似的，更经典的（和相同的）问题，给出一个带有数字，加法和乘法的公式，它给出了什么括号最大值，例如
6 + 1 * 2 成为（6 + 1）* 2 超过 6+（1 * 2）。

让我们表示我们的输入 a1到实数和o（1），... o（n-1） * 或 + 。我们的方法将如下，我们将观察代表a1，... aj的最大公式（在薄化之后）的子问题F（i，j）。我们将创建一个这样的子问题表，并观察F（1，n）正好是我们正在寻找的结果。

定义

  F（i，j）
 
  - 如果我> j返回0 //没有负长度的子公式
 - 如果i = j返回ai //一个数字的最大公式是数字
  - 如果i< j返回i（包括）和j（不包括）之间的所有m的最大值：
 F（i，m）（o（m））F（m + 1，j）//检查所有地方是否存在可能的硬化插入
  

这可以通过所有可能的选项。正确的TProof通过感应尺寸n = ji完成，并且很简单。

让我们进行运行时分析：

如果我们不为动态保存较小子问题的值，则运行速度相当慢，但是我们可以使这个算法在 O（n ^ 3）

我们创建一个* n表T，其中索引i处的单元格j包含F（i，j）填充F（i，i ）和小于i的j的F（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 你得到你想要的价值。

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.

How I am approaching the problem:

 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.

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).

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.

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

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

Lets go through runtime analysis:

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)

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.

Now back to your problem

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.

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