Ich denke über den Algorithmus für das folgende Problem nach (gefunden auf carrercup):

Gegeben ein Polygon mit N Ecken und N Kanten. Es gibt eine Ganzzahl (kann negativ sein) für jeden Scheitelpunkt und eine Operation in Menge (*, +) für jede Kante. Jedes Mal, wenn wir eine Kante E aus dem Polygon entfernen, führen wir die beiden Scheitelpunkte, die durch die Kante (V1, V2) verbunden sind, zu einem neuen Scheitelpunkt mit dem Wert V1 op (E) V2 zusammen. Der letzte Fall wären zwei Eckpunkte mit zwei Kanten, das Ergebnis ist der größere. Rückgabe Der maximale Ergebniswert kann aus einem bestimmten Polygon ermittelt werden.

Ich denke, wir können einfach gierig vorgehen. Das heißt für Polygon mit k Kanten finden Sie ein Paar (p, q), das beim Zusammenfallen die maximale Anzahl ergibt: (p, q) = max ({i Operation j: i, j - benachbarte Kanten)

Rufen Sie dann einfach eine Rekursion für Polygone auf: 1. Lassen Sie die Funktion CollapseMaxPair (P (k)) - Polygon mit k Kanten erhalten und 'kollabiertes' Polygon mit k-1 Kanten zurückgeben. 2. Dann unsere Rekursion:

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

Was denkst du?