Myślę o algorytmie dla następującego problemu (znalezionego na carrercup):

Biorąc pod uwagę wielokąt z N wierzchołkami i N krawędziami. Na każdym wierzchołku jest liczba int (może być ujemna), a na każdej krawędzi operacja w zbiorze (*, +). Za każdym razem usuwamy krawędź E z wielokąta, łączymy dwa wierzchołki połączone krawędzią (V1, V2) z nowym wierzchołkiem o wartości: V1 op (E) V2. Ostatni przypadek to dwa wierzchołki o dwóch krawędziach, wynik jest większy. Zwróć maksymalną wartość wyniku można uzyskać z danego wielokąta.

Myślę, że możemy użyć tylko zachłannego podejścia. To znaczy. dla wielokąta o k krawędziach znajdź parę (p, q), która tworzy maksymalną liczbę podczas zwijania: (p, q) = max ({i operacja j: i, j - sąsiadujące krawędzie)

Następnie wywołaj rekurencję na wielobokach: 1. Niech funkcja CollapseMaxPair (P (k)) - pobiera wielokąt z krawędziami k i zwraca „zwinięty” wielokąt z krawędziami k-1 2. Następnie nasza rekurencja:

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

Co myślisz?