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?