h2. 'MMsir':problema/mmsir

Vom rezolva problema in $o(n)$ folosind $2$ contori, $st$ si $dr$, si $2$ vectori, $h[i]=1$ daca si numai daca {$a[i-1] < a[i] > a[i+1]$} sau {$a[i-1] > a[i] < a[i+1]$}, si $schimb[i]$ care va fi egal cu cel mai mic $j$ cu proprietatea ca $h[j]=1$ si $j>i$. De aici vom incepe sa construim solutia astfel: initial $dr$ va fi egal cu cel mai mic $i$ cu proprietatea ca secventa $1 i$ isi schimba monotonia de $k$ ori, iar $st$ va fi egal cu $1$. Incepem sa incrementam $dr$ cu cate o unitate si de fiecare data adunam la solutie $schimb[st] - st$. Atunci cand $h[dr-1] = 1$, $st$ ia valoarea $schimb[st]$.

Vom rezolva problema in $o(n)$ folosind $2$ contori, $st$ si $dr$, si $2$ vectori, $h[i]=1$ daca si numai daca {$a[i-1] < a[i] > a[i+1]$} sau {$a[i-1] > a[i] < a[i+1]$}, si $schimb[i]$ care va fi egal cu cel mai mic $j$ cu propietatea ca $h[j]=1$ si $j>i$. De aici vom incepe sa construim solutia astfel: initial $dr$ va fi egal cu cel mai mic $i$ cu propietatea ca secventa $1 i$ isi schimba monotonia de $k$ ori, iar $st$ va fi egal cu $1$. Incepem sa incrementam $dr$ cu cate o unitate si de fiecare data adunam la solutie $schimb[st] - st$. Atunci cand $h[dr-1] = 1$, $st$ ia valoarea $schimb[st]$.

Pentru o rezolvare brute cu complexitate $o(n^2)$ se acordau $30$ de puncte.