Intuiție / reformulare
Imaginează-ți cartonașele ca pe niște piese de domino așezate în linie. Fiecare piesă are un număr la stânga și unul la dreapta. Singurul lucru care contează este lipitura dintre două piese vecine: locul unde numărul din dreapta uneia atinge numărul din stânga celei următoare. Dacă cele două numere care se ating sunt egale, spunem că lipitura „se potrivește”.
Toate cele trei cerințe se rezolvă uitându-te la aceleași lipituri:
- C1 — câte lipituri se potrivesc (numărul de perechi vecine bune);
- C2 — cea mai lungă bucată neîntreruptă de piese legate prin lipituri bune (măsurată în cartonașe);
- C3 — câte astfel de bucăți au lungimea maximă.
Nu trebuie să compari cartonașe care nu sunt vecine: o serie se rupe imediat ce o lipitură nu se potrivește.
Ideea cheie
Parcurg șirul o singură dată și țin minte lungimea seriei curente, adică de câte cartonașe la rând am legat până acum fără întrerupere. Pornesc cu o serie de cartonaș (primul). La fiecare lipitură:
- dacă se potrivește, seria curentă crește cu un cartonaș (și am o pereche bună în plus pentru C1);
- dacă nu se potrivește, seria s-a terminat: o „închid” și pornesc o serie nouă, tot de la cartonaș.