Z góry dzięki.

Przetwarzamy wartości 1, 2, ..., n rosnąco, decydując dla każdej czy bierzemy ją do naszego podciągu. Jeśli bierzemy wartość x, to liczba inwersji zwiększa się o to ile wzięliśmy już wcześniej wartości po prawej stronie od x.

Naiwnie to co musielibyśmy pamiętać to zbiór pozycji które wybraliśmy, to dałoby 2^n stanów.

Zauważmy, że jeśli pewne z już przetworzonych pozycji tworzy w permutacji spójny przedział, to nie interesuje nas już dokładnie które z tych pozycji wybraliśmy do podciągu, a jedynie ich liczba. Sklejając stany w ten sposób dostajemy ich około 3^(n/3) w najgorszym wypadku.

Why 3^(n/3)?

Liczba możliwych stanów, to iloczyn po wszystkich przedziałach 1 + długość przedziału. Suma wszystkich liczb, które wymnażamy jest równa n + 1. Jak mamy iloczyn a_1 * a_2 * ... * a_k, to rozbijamy a_1 na (a_1^(1 / a_1)) ^ a_1. Dostajemy w ten sposób iloczyn mający a_1 + a_2 + ... + a_k czynników, każdy z nich jest postaci x^(1/x). Dla całkowitych x maxymalna wartość x^(1/x) jest osiągalna dla x = 3, stąd taki iloczyn szacuje się przez (3^(1/3))^(a_1 + a_2 + ... + a_k), czyli O(3^(n / 3))

Ja dzielę wykres permutacji na cztery ćwiartki, i próbuję wszystkie podzbiory w lewej górnej i w prawej dolnej. Podzbiory w prawej górnej i lewej dolnej mogę wybrać niezależnie, bo liczba inwersji pomiędzy nimi zależy tylko od wielkości zbiorów. Czas działania O(2^(0.75 n)).