Indicatii traseu3

Solutia 5 – 90 puncte -- O(N * M * N)

Vom procesa elementele în ordine crescătoare, și dacă la un moment dat avem o valoarea v, aflată la coordonatele (x, y) vrem să aflăm cel mai lung traseu care se termină la această poziție.

Asta înseamnă ca trebuie ca traseul să înceapă la una din valorile mai mici, valori care au fost deja procesate. Iar dintre acestea se dorește cea la distanță maximă de (x, y) mai sus și mai la stânga.

Putem ține astfel pentru fiecare linie cea mai din stânga poziție procesată: best[i] = y minim astfel încât (i, y) a fost deja procesat. Când suntem la valoarea v de la poziția (x, y) putem verifica toate liniile de la 1 la x, și important este doar cea mai din stânga poziție procesată.

Deci pentru linia i, ne uităm la best[i]

(a) Dacă best[i] <= y, atunci traseul care începe la (i, best[i]) și se termină la (x, y) e un potențial traseu maxim. Dacă este mai lung decât cel mai lung traseu găsit pana la momentul actual, actualizăm răspunsul.
(b) Dacă best[i] > y, sau best[i] încă nu a fost calculat nu facem nimic.
Deoarece pentru fiecare valoare s-au procesat maximum N linii, complexitatea finală este O(N * M * N).