Estou pensando no algoritmo para o seguinte problema (encontrado no carrercup):

Dado um polígono com N vértices e N arestas. Existe um número int (pode ser negativo) em cada vértice e uma operação em set (*, +) em cada borda. A cada vez, removemos uma aresta E do polígono, mesclamos os dois vértices ligados pela aresta (V1, V2) a um novo vértice com valor: V1 op (E) V2. O último caso seria dois vértices com duas arestas, o resultado é o maior. Retornar o valor máximo do resultado pode ser obtido de um determinado polígono.

Acho que podemos usar apenas uma abordagem gananciosa. Ou seja para polígonos com k arestas encontre um par (p, q) que produza o número máximo ao colapsar: (p, q) = max ({i operação j: i, j - arestas adjacentes)

Em seguida, basta chamar uma recursão em polígonos: 1. Deixe a função CollapseMaxPair (P (k)) - obter polígono com k arestas e retorna polígono 'colapsado' com k-1 arestas 2. Em seguida, nossa recursão:

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

O que você acha?