Интервью Google: найдите максимальную сумму многоугольника

Дан многоугольник с N вершинами и N ребрами. В каждой вершине есть число int (может быть отрицательным) и операция в наборе (*,+) на каждом ребре. Каждый раз, когда мы удаляем ребро 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 .

Могу ли я сделать лучше, чем это?


algorithm data-structures matrix-multiplication
person Peter    schedule 19.01.2013    source источник
comment
Я не знаю, почему одна и та же группа людей каждый день голосует против моих проблем. Ребята, у вас есть какие-то личные обиды, разве я не принял ваш ответ когда-то или около того? что в этом слишком локализовано или не по теме. это проблема алгоритма, я написал свой подход, я ищу более оптимизированный метод, если он существует, я был очень откровенен, что это проблема интервью Google, что еще хотят люди, которые голосуют за закрытие   -  person Peter    schedule 19.01.2013
comment
Может быть, некоторые думают, что это портит интервью будущим кандидатам? Я бы хотел, чтобы люди приводили причины для отрицательных голосов и т. Д.   -  person djna    schedule 19.01.2013
comment
дубликат stackoverflow.com/questions/14401923/   -  person AndyG    schedule 19.01.2013
comment
там до сих пор нет решения   -  person Peter    schedule 19.01.2013
comment
Я добавил решение вашей проблемы, есть более эффективные решения, но они намного сложнее, дайте мне знать, что вы думаете.   -  person Benjamin Gruenbaum    schedule 19.01.2013

Ответы (2)


arrow_upward
5
arrow_downward

Как вы правильно определили (пометили), это действительно очень похоже на задачу умножения матриц (в каком порядке я умножаю матрицы, чтобы сделать это быстро).

Это может быть решено полиномиально с использованием динамического алгоритма.

Вместо этого я собираюсь решить аналогичную, более классическую (и идентичную) задачу, учитывая формулу с числами, сложением и умножением, какой способ заключения в скобки дает максимальное значение, например, 6+1 * 2 становится (6+1)*2, что больше, чем 6+(1*2).

Обозначим наши входные a1 to 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 T, в которой ячейка с индексом i, j содержит F (i, j), заполняя F (i, i) и F (i, j) для j, меньшего, чем i, выполняется в O (1) для каждую ячейку, так как мы можем вычислить эти значения напрямую, затем идем по диагонали и заполняем F(i+1,i+1) (что мы можем сделать быстро, так как мы уже знаем все предыдущие значения в рекурсивной формуле), мы повторяем это n раз для n диагоналей (на самом деле все диагонали в таблице), и заполнение каждой ячейки занимает (O (n)), поскольку каждая ячейка имеет O (n) ячеек, мы заполняем каждую диагональ за O (n ^ 2), что означает, что мы заполняем все таблица в O (n ^ 3). После заполнения таблицы мы, очевидно, знаем F (1, n), что является решением вашей проблемы.

Порядок, в котором мы заполняем нашу таблицу

Теперь вернемся к вашей проблеме

Если вы переведете многоугольник в n разных формул (по одной для начала в каждой вершине) и запустите на нем алгоритм для значений формулы, вы получите именно то значение, которое хотите.

person Benjamin Gruenbaum    schedule 19.01.2013

arrow_upward
0
arrow_downward

Я думаю, вы можете уменьшить потребность в поиске методом грубой силы. Например: если есть цепочка

x + y + z

Вы можете заменить его одной вершиной, значение которой является суммой, вы не можете сделать лучше, чем это. Вам нужно выполнить умножение после сложения, когда вы имеете дело с целыми числами +ve. Итак, если все положительно, просто уменьшите все + цепочки, а затем умножьте.

Так что остаются случаи, когда есть -ve чисел. Мне кажется, что стратегия для одного -ve числа довольно очевидна, для двух -ve чисел есть несколько случаев (помните, что - x - положительно), а для более чем 2 -ve чисел это кажется сложным: - )

person djna    schedule 19.01.2013