De ce contează?
Imaginează-ți rafturile dintr-un magazin de scule. Ai un singur cui de bătut, dar o cutie întreagă de ciocane: unul mic pentru pioneze, unul mare pentru cuie groase, un ciocan de cauciuc pentru gresie. Nu inventezi un ciocan nou de fiecare dată — te uiți la cui și ALEGI ciocanul potrivit. În capitolul ăsta ai învățat deja câteva „ciocane" pentru intervale dintr-un vector. Lecția asta nu adaugă unul nou: te învață cum să te uiți la o problemă și să recunoști care unealtă o sparge.
Ideea-cheie
Înainte de orice tehnică, trebuie să fii sigur ce căutăm. Două cuvinte se confundă tot timpul:
- O subsecvență este o felie lipită din vector — pozițiile
l, l+1, ..., runa lângă alta, fără goluri. În[5, 3, 8, 1, 9], felia[3, 8, 1](pozițiile 2, 3, 4) este o subsecvență. - Un subșir este o selecție de elemente în ordine, dar nu neapărat vecine — ai voie să sari peste poziții. În același vector,
[5, 8, 9](pozițiile 1, 3, 5) este un subșir, dar nu o subsecvență, fiindcă ai sărit poziții.
Toate uneltele din acest capitol lucrează pe subsecvențe: felii continue, descrise de un capăt stânga l și un capăt dreapta r.
Testul rapid: dacă poți descrie ce cauți doar prin „de la poziția l până la poziția r", e o subsecvență și tehnicile de aici se aplică. Dacă trebuie să spui „aleg unele elemente și sar peste altele", e un subșir — altă poveste, alte unelte (de obicei mai târziu, la programare dinamică).