Estoy pensando en el algoritmo para el siguiente problema (que se encuentra en Carrercup):

Dado un polígono con N vértices y N aristas. Hay un número int (podría ser negativo) en cada vértice y una operación en conjunto (*, +) en cada borde. Cada vez que eliminamos un borde E del polígono, combinamos los dos vértices unidos por el borde (V1, V2) a un nuevo vértice con valor: V1 op (E) V2. El último caso sería dos vértices con dos aristas, el resultado es el más grande. Devolver el valor de resultado máximo puede obtenerse de un polígono dado.

Creo que podemos usar solo el enfoque codicioso. Es decir. para el polígono con k bordes, encuentre un par (p, q) que produzca el número máximo al colapsar: (p, q) = máx ({operación i: j, i, j - bordes adyacentes)

Luego llame a una recursión en los polígonos: 1. Deje la función CollapseMaxPair (P (k)): obtiene el polígono con k bordes y devuelve el polígono "colapsado" con k-1 bordes 2. Luego nuestra recursión:

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

¿Qué piensas?