h2(#operatii). 'Operatii':problema/operatii

h2(#operatii). 'Operatii':problema/operatii
 
Problema admite multe rezolvari si a fost propusa pentru o departajare a concurentilor. Un prim algoritm ar fi selectarea la fiecare pas a secventei de lungime maxima ce contine numai elemente nenule si decrementarea cu o unitate a tuturor elementelor secventei. Procedeul se repeta cat timp exista o secventa cu elemente nenule (cat timp vectorul nu este nul). Deoarece la fiecare pas s-a selectat secventa de lungime maxima, numarul final de operatii va fi minim posibil. Aceasta solutie obtine 20-40 de puncte, in functie de prezenta optimizarilor.
Complexitatea optima in care se poate rezolva problema este {$O(N)$} si exista mai multe rezolvari diferite ce au aceasta complexitate. Una din rezolvari este urmatoarea: fie $MAX$ maximul elementelor din vectorul {$v$}. Retinem $MAX$ liste, in a $i$-a lista avand memorate pozitiile din vector pe care apare numarul $i$. Pornim de la vectorul nul si inseram pe rand numerele {$1$}, {$2$}, ... {$MAX$}. Calculam la fiecare pas $i$ numarul de operatii necesar pentru a ajunge de la vectorul