h3. (problema usoara, clasele 11-12)

Prima observatie este aceea ca valoarea maxima pe care o poate lua $S$ este {$N * (N-1) / 2$}, sirul  $a$ fiind egal cu (0, 1, 2... N-1), iar valoarea minima {$-N * (N-1) / 2$}, caz in care sirul $a$ este egal cu {0, -1, -2... -(N-1)). Daca notam cu {$D[N][S]$} numarul de 1-siruri cu $N$ termeni care au suma elementelor $S$, atunci se observa ca {$D[N][S] = D[N-1][S-(N-1)] + D[N-1][S+(N-1)]$}, deoarece avem doua posibilitati de alegere pentru al doilea element (1 sau -1), si fiecare alegere poate fi interpreta ca o translatie pentru fiecare din elementele urmatoare cu 1 sau -1. Pentru a evita folosirea indicilor negativi pentru suma este suficient sa observam ca {$D[N][S] = D[N][-S]$}, pentru orice {$S > 0$}, relatie evidenta din faptul ca se poate forma o bijectie intre 1-sirurile cu suma S si cele cu suma -S printr-o simpla inmultire cu -1.

Prima observatie este aceea ca valoarea maxima pe care o poate lua $S$ este {$N * (N-1) / 2$}, sirul {$a$} fiind egal cu {$(0, 1, 2... N-1)$}, iar valoarea minima {${@-N * (N-1) / 2@}$}, caz in care sirul este egal cu {$(0, {@-1@}, {@-2@}... {@-(N-1)@})$}. Daca notam cu {$D[N][S]$} numarul de 1-siruri cu $N$ termeni care au suma elementelor $S$, atunci se observa ca {$D[N][S] = D[N-1][S-(N-1)] + D[N-1][S+(N-1)]$}, deoarece avem doua posibilitati de alegere pentru al doilea element (1 sau -1), si fiecare alegere poate fi interpreta ca o translatie pentru fiecare din elementele urmatoare cu 1 sau -1 ( deci in total o translatie in functie de suma de {$N-1$}, cu plus sau cu minus ). Pentru a evita folosirea indicilor negativi pentru suma este suficient sa observam ca {$D[N][S] = D[N][-S]$}, pentru orice {$S > 0$}, relatie evidenta din faptul ca se poate forma o bijectie intre 1-sirurile cu suma {$S$} si cele cu suma {${@-S@}$} printr-o simpla inmultire cu -1. Pentru ca algoritmul sa se incadreze in limita de memorie este suficient sa retinem doar ultimele doua linii din tabloul $D$. Un astfel de algoritm obtine punctajul maxim.

h2. Diviz