Najduzi rastuci podniz

Nedavno sam radio zadatak “Najduzi rastuci podniz” sa sajta Bubblebee i resio ga. Slozenost mog resenja je bila n^2, pa sam pogledao resenje tog zadatka, koje je imalo slozenost nlogn (sa binarnom pretragom), ali mi nije bilo bas najjasnije objasnjenje resenja, niti sta znaci vector::iterator (nejasan mi je samo deo ::iterator, upoznat sam sa vektorima). Naime, u resenju je deklarisana promenljiva koja je jednaka rezultatu binarne pretrage, koja vraca celobrojnu vrednost, pa mi nije jasno zasto je ona vektor. Da li bi neko mogao detaljnije da mi objasni resenje tog zadatka?
Hvala unapred!

video
ugl, imas niz lis[], ako je trenutni element veci od poslednjeg u nizu, dodaj ga na kraj, ako nije, binary search gde treba da zamenis element

Taj deo mi je sada jasan, ali u ovom videu postoji jos jedan niz - parents. Cemu on sluzi?
P.S.
I molim vas ako bi neko mogao da mi objasni i pitanje u vezi sa vector::iterator iz posta.
Hvala @Hoxen!

Iterator je pokazivac na mesto u vektoru, koliko ja znam. Moze samo da prima ++ i --. Ima ga za svaki kontainer npr. Multiset< int >::iterator. vector< int >::iterator (bez razmaka se pise nego mi zeza nesto :slight_smile:) je iterator koji pokazuje na int u vektoru. Definisemo petlju da je it = nasvector.begin(), povecava se (it++) dok vazi it != nasvector.end(), jer end zapravo nista ne pokazujw nego mora da postoji samo da oznaci kraj. Da bismo dobili int iz iteratora pisemo *it. Ja mislim da ne mora da se koristi iterator za vektor, a da u c++11 moze da se koristi i auto, ali korisno mi je za multiset, stack, queue, listu itd. Naravno, ako je vector::iterator it, *it vraca char, to nije vector, nego iterator za odredjeni tip vektora(ili bilo kog drugog kontejnera). *it = 5, menja 5 za bilo sta sto je tu bilo, a brisanje iteratora je vec kompilkovanije…

1 Like

Hvala, sad mi je jasno!