$A{~i,j,0~} = max(A{~i-1,j,0~}, A{~i-1,j,1~})$
Am redus complexitatea la $O(N*B)$ si memoria la $O(N)$, o imbunatatire substantiala.
Deoarece sirul este circular, putem rezolva problema aplicand de N$$ ori dinamica de mai sus considerand sirul liniar si alegand fiecare pozitie ca fiind pozitia initiala, dar aceasta solutie depaseste cu mult limita de timp pe cazul cel mai defavorabil. Totusi, aceasta idee ar fi adus $10$ teste din cele $14$. Cu un mic truc, si anume alegerea aleatorie a pozitiei de start cat timp nu s-a depasit timpul de executie, s-ar mai fi putut obtine inca $2$ teste, in total $12$ (desi aceasta rezolvare nu obtine solutia optima pe testele foarte mari).
Deoarece sirul este circular, putem rezolva problema aplicand de $N$ ori dinamica de mai sus considerand sirul liniar si alegand fiecare pozitie ca fiind pozitia initiala, dar aceasta solutie depaseste cu mult limita de timp pe cazul cel mai defavorabil. Totusi, aceasta idee ar fi adus $10$ teste din cele $14$. Cu un mic truc, si anume alegerea aleatorie a pozitiei de start cat timp nu s-a depasit timpul de executie, s-ar mai fi putut obtine inca $2$ teste, in total $12$ (desi aceasta rezolvare nu obtine solutia optima pe testele foarte mari).
Putem scapa de faptul ca sirul este circular mult mai elegant, aplicand de 2 ori dinamica: odata cum am zis mai sus (acoperind cazul cand pozitiile $N$ si $1$ nu sunt in aceeasi secventa de pozitii consecutive) si inca odata fortand sa existe o secventa de utilitati aleasa care contine pozitiile $N$ si $1$. A doua dinamica se poate obtine exact ca mai sus, aplicand aceeasi idee doar ca se initializeaza $A{~1,1,1~}=U{~1~}$ in loc de 0, si apoi pentru fiecare $i$ se verifica rezultatul curent cu $max(A{~i,B-(N-i),0~}, A{~i,B-(N-i),1~} + suma U{~i+2~}...U{~N~})$. Pentru a se incadara in limita de 0.3s trebuie acordata o mare grija la implementare, de exemplu, optimizand dinamica de mai sus de la $2*N$ memorie (ultimele doua linii din matricea $A$) la doar $N$ pastrand doar ultima linie si parcurgand indicele $j$ descrescator.
