h1. Solutii

h3. (clasele 9-10)
 

h2. Maxsecv
Se observa ca secventa maxima de $1$ care se poate obtine are lungimea egala cu suma primelor doua secvente maxime din vectorul original. Printr-o operatie descrisa se pot alatura cu usurinta cele doua secvente.
Pentru obtinerea unei solutii liniare e suficient sa parcurgem vectorul de la stanga la dreapta si sa updatam la fiecare pas lungimea secventei curente de $1$. In momentul in care ajungem la capatul unei astfel de secvente facem un update pentru primul si al 2-lea maxim, dupa caz.

h3. (clasele 9-10)
 
...

h2. Chernel

Problema se poate rezolva folosind metoda programarii dinamice. Se construieste matricea $A{~t,i~}$ in care se retine valoarea totala a amenzilor ce poate fi data pana la momentul $t$ astfel incat la momentul $t$ sa fim in intersectia {$i$}. Pentru toate muchiile ({$j,i$}) de cost $c$ vom compara {$A{~t,i~}$} cu {$A{~t-c,j~}$} alegand maximul dintre aceste valori. De fapt ar trebui inspectate toate valorile {$A{~t-c,j~}$} {$A{~t-c-1,j~}$} ... {$A{~1,j~}$} {$A{~0,j~}$} dar este clar ca maximul acestor valori se afla in {$A{~t-c,j~}$}. Deasemenea trebuie considerat cazul cand politistul sta pe loc deci ne vom uita si la valoarea din {$A{~t-1,i~}$}. Apoi politistul va da toate amenzile posibile la momentul respectiv in intersectia respectiva deci vom aduna respectiva suma la {$A{~t,i~}$}.
Avand construita aceasta matrice se poate raspunde in $O(1)$ la fiecare intrebare.

Complexitatea totala va fi $O(Tmax * M)$ ca timp si $O( Tmax * N )$ ca memorie.

Complexitatea totala va fi $O(Tmax * M)$ ca timp si $O(Tmax * N)$ ca memorie.

h2. Secventa 5