Złożoność obliczeniowa algorytmu do maksymalizowania sumy.

Zadany jest ciąg liczb całkowitych, mniejszych od 200. Maksymalnie jest takich liczb 1000. Usuwamy jedną z tych liczb o indeksie i (nie mogą to być skrajne liczby) i dodajemy liczby o indeksach i-1, i, i+1 do sumy. Krok ten powtarzamy do czasu, aż ilość elementów w zbiorze jest większa od 2. Musimy zmaksymalizować tak otrzymaną sumę.

Chcąc to robić brute-forcem i sprawdzając taką sumę dla każdej z możliwych kombinacji dostajemy algorytm o złożoności O(n!). Pan Profesor zaproponował rozwiązanie, w którym dla zadanego ciągu zakładamy, że usuwając daną liczbę na końcu dostaniemy największą wartość. Wybrana liczba tworzy nam dwa ciągi (jedna sekwencja od liczby na pozycji 0 do indeksu wybranej liczby, druga sekwencja od tej liczby, do ostatniej) - i wywołujemy to rekurencyjnie (albo coś w ten deseń).

Ponoć ta druga metoda, ma już złożoność tylko O(n^3). Pytanie, skoro sprawdzając wszystkie możliwe sposoby brute-forcem dostajemy złożoność O(n!), a poszukując rozwiązania na ten sam problem drugim sposobem (co według mnie i tak sprowadza się do sprawdzenia wszystkich możliwości) dostajemy już inną (dużo mniejszą) złożoność. Skąd ta różnica?

1. Pierwsze pytanie jest oczywiste -> masz n liczb w ciągu i chcesz je usuwać w jakiejś kolejności. Na ile sposobów można ustawić n liczb? Czyli ile jest różnych permutacji? n!
2. Trudno ocenić drugi pomysł skoro nie potrafisz opisać konkretnie jak ten algorym ma działać... Ale zgaduje ze to jakiś algorytm dynamiczny/zachłanny

Niemniej jeśli chodzi o pytanie ogólne: to normalne że ten sam problem można rozwiązać wieloma algorytmami, jedne są szybsze inne wolniejsze. Mozesz np. sortować liczby w czasie O(nlogn) jakimś merge sortem, ale możesz też robić to bogo-sortem, czyli brać losową permutacje zbioru i sprawdzać czy jest posortowana i jeśli nie jest to powtórzyć. Takie "sortowanie" tez ma złożoność O(n!)

co według mnie i tak sprowadza się do sprawdzenia wszystkich możliwości

Rzecz w tym że się nie sprowadza ;) Tak jak z tym sortowaniem -> nie trzeba sprawdzić wszystkich możliwych permutacji żeby znaleźć tą posortowaną.

Zacznij może naukę od czegoś łatwiejszego, jak problem "wydawania reszty". Jak wydać kwotę X stosując jak najmniejszą liczbę monet? Czy uważasz ze trzeba to robić brute-force, testując wszystkie możliwości, czy jednak da sie szybciej?

No tak, wiem że będzie n! możliwych permutacji, zastanawiało mnie bardziej to, dlaczego - mimo, że i tak sprawdzimy każdą permutację - dostaniemy różne złożoności. Tak jest to algorytm dynamiczny i wydaje mi się, że teraz zrozumiałem o co chodzi. O ile dobrze zrozumiałem, to mając jakąś tablicę liczb:
{10, 20, 25, 30, 40, 50, 60, 65, 70} wybieramy dowolną liczbę. załóżmy że jeżeli wybierzemy ostatnią liczbę 40 to otrzymamy największą sumę. Czyli w ostatniej iteracji dodamy 10+40+70, a sama liczba podzieli nam wejściową tablicę na dwie: {10,20, 25, 30,40} i {40,50,60, 65, 70}. Na tych dwóch mniejszych tablicach wykonujemy tak samo - wybieramy liczbę i teraz w przedostatniej operacji dodamy np. dla wybranej 25: 10+25+40. To wykonujemy dotąd, aż rozmiar tablicy będzie równy 3. Gdy będzie równy 3 - już nie dzielimy. Fizycznie nie musimy nawet usuwać danej liczby (co wiązałoby się z kopiowaniem listy).

Chyba jednak nie rozumiesz tego algorytmu, bo losowe wybieranie raczej nigdzie cię nie zaprowadzi ;) Poza tym pomijasz kwestię że liczby sie przesuwają! Założmy że masz przypadek
50 1 30 50

sensownie byłoby usunąć najpierw 1 a potem 30, ale zauważ że w takim układzie w ostatnim kroku usuniesz 30 a do sumy dodasz 50+50 mimo że początkowo ta pierwsza 50 wcale nie leżała koło 30
Jeszcze raz: wcale nie trzeba sprawdzać wszystkich permutacji! Zastanów się trochę nad tymi przykładami które dałem wyżej -> bogo-sort i wydawanie reszty.

Wiem, że usuwając liczbę liczby "po prawej" się przesuwają. Nie mówię też, o losowym wybieraniu, a raczej o sprawdzeniu każdej z możliwości tylko tym algorytmem - tylko, że dla mnie jest to bruteforce.
Wiem też, że nie trzeba sprawdzać każdej permutacji, choćby z tego powodu że mając jakiś ciąg np: 1,2,3,4,5,6,7 można najpierw usunąć 2, potem 3 lub na odwrót: najpierw 3, potem 2. Wtedy można odrzucić sytuacje w której dotychczasowa suma będzie mniejsza. Myślałem też nad rozwiązaniami, w których w danej chwili brałbym największy wynik - nie tędy droga. Kolejny sposób jaki mi przyszedł do głowy to sposób, w którym nie patrzyłbym na liczbę o indeksie i, tylko na jej sąsiadów i wtedy bym wyszukiwał takiej liczby, której suma sąsiadów byłaby największa. W sytuacji gdy byłyby dwie lub więcej 3 takie liczby, to usuwałbym tą która byłaby najmniejsza. To też nie działa. Usuwanie liczby która stoi przy największej, nie rozwiązuje tego problemu. Kolejny algorytm nad którym myślałem, to algorytm do wyznaczania maksymalnej drogi. Wierzchołkami byłyby liczby, a krawędziami - suma liczby i jej sąsiadów, po jej usunięciu. Tylko dalej jest n! permutacji, a nie jest możliwe utworzenie takiej macierzy a i tak, ostatnia wybrana liczba może spowodować, że rozwiązanie nie da poprawnego wyniku Parę innych pomysłów też miałem, ale żaden się nie sprawdził. Zgadzam się, że żeby zaleźć rozwiązanie trzeba patrzeć na ostatnią liczbę, ale według mnie bez znajomości sum każdej możliwej opcji, w przedostatniej iteracji to niezbyt dużo daje.

Edit: poproszę jeszcze raz o prowadzącego, żeby wytłumaczył jeszcze raz ten algorytm, ale to dopiero w następny wtorek.
Edit 2: Od jakiej "strony" mógłbym podejść żeby rozwiązać ten problem?