Witam serdecznie
Mam do napisania program, który dla pewnej tablicy wypełnionej danymi wejściowymi znajdzie najdłuższy ciąg rosnący liczb.
Nie wiem jak napisac odpowiedni algorytm do tego programu.
Dla przykładu dla tablicy z danymi wejściowymi:
3,12,4,16,2,5,7,12,16,3,2,4,8,3,4,2,3,8,5,6,3,6
Program powinien wyświetlic:
2,5,7,12,16
Mógłby mnie ktoś nakierowac w jaki sposób taki program napisac?
Skopiuj ciąg i posortuj go. Następnie wykonaj algorytm "Najdłuższy wspólny podciąg" dla ciągu twojego i posortowanego ;)
Informacje NWP znajdziesz na wikipedii lub w Cormenie :]
Znam jeszcze algorytm n*log(n) do tego zadania (ten wyżej to n^2) ale jest dużo bardziej skomplikowany.
Czy ten podciąg ma być spójny?
Jeżeli tak, to jest banalne rozwiązanie w czasie O(n).
Natomiast jeśli nie, to istnieje bardzo proste rozwiązanie w czasie O(n lg n) za pomocą n krotnego wyszukiwania binarnego po tablicy zawierającej najlepszych(o jak najniższej pozycji w ciągu) dotychczas znalezionych kandydatów na początki podciągów kolejno długości 1,2,3...