W google pełno jest informacji jak znaleźć najdłuższy rosnący podciąg, ale brakuje informacji jak policzyć, ile takich wszystkich rosnących podciągów jest (albo źle formułowałem zapytania..). Czy ktoś zna jakiś efektywny algorytm mogący posłużyć do tego celu? A może jakieś linki? Z góry dzięki za każdą pomoc :)
0
0
Ale wszystkich najdłuższych czy w ogóle? Tzn czy dla:
1 2 3 4 5
mamy jeden podciąg (1,2,3,4,5) czy też (1,2), (2,3), (3,4), (4,5), (1,2,3), (2,3,4) ... itd
Ogólnie to nie widzę tu w ogóle problemu. Iterujesz po ciągu od początku i dopóki wyraz następny jest większy od poprzedniego to masz cały czas ciąg rosnący. Jeśli kolejny wyraz jest mniejszy to zaczyna ci sie nowy potencjalny podciąg i jeśli poprzedni podciąg miał długość większą od 1 to go zliczasz.
0
Wszystkich w ogóle. Dla 1 2 3 4 5 wg tego co policzyłem na kartce powinno wyjść 26 takich podciągów.
Ten algorytm co przedstawiłeś niezbyt zadziała (albo po prostu źle go rozumiem) - założmy ciąg: 5 15 7 10 3 20
Idąc jak pokazałeś będziemy mieli ciągi:
5 15
7 10
3 20
omijamy w ten sposób wiele podciągów, takich jak:
5 7
5 10
5 7 10 20
5 20
Wydaje mi się że założyłeś, że podciąg ma być spójny - tak nie jest, nie pisze też o tym w temacie :) Ale moja wina, mogłem to lepiej zaznaczyć.
0
Jeśli pamięć mnie nie myli to problem o którym piszesz da się rozwiązać w czasie O(nlogn) za pomocą
zmodyfikowanego algorytmu szukania najdłuższego podciągu. O najdłuższym podciągu można przeczytać to: http://informatyka.wroc.pl/node/402?page=0,0
Trzeba zastosować programowanie dynamiczne, opis jest na drugiej stronie. Modyfikacja (czyli właściwy algorytm) polega na wprowadzeniu tablicy ILE.
ILE[i] - liczba ciągów rosnących kończących się w elemencie z i-tej pozycji. Skanując wejściowy ciąg z lewej do prawej odpowiedniu aktualizujemy ILE.
Jeśli będzie trzeba mogę podać więcej szczegółów.
0
Kiedy próbowałem samemu wymyślać rozwiązanie, zanim tu zapytałem, zaimplementowałem coś takiego: http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming (drugie rozwiązanie - O(n log n)). Próbowałem je zmodyfikować, tak, żeby pasowało do mojego problemu, ale nie wyszło. Sądząc po złożoności to jest podobny algorytm (jeszcze tego linku co podałeś nie analizowałem - już się za to zabieram).
Więc jeśli mógłbyś podać więcej szczegółów co do tego, jak należy aktualizować tą tablicę ILE, byłbym wdzięczny.