Dany jest ciąg liczb a_1, ..., a_n
Znajdź liczbę podciągów ściśle rosnących (niekoniecznie spójnych).
Proponuję: dynamik + słownik:
W AVL kluczem jest wartość elementu, węzły przechowują dodatkowo ilość podciągów ściśle rosnących kończących się na tym elemencie (klucz).
Gdy chcę policzyć ile podciągów kończy się na danym elemencie a, to:
x = węzeł w drzewie, taki że jego klucz jest największym mniejszym elementem
niż a.
Więc do wyniku doliczam 1 + x.ilosc oraz wstawiam do do drzewa. To jest O(nlog(n)). Czy to jest poprawne ? Czy da się O(n) ?
