sum:  $ -2  0 2 4 7 8 10 11$
 ind:   $ 4  0 1 4 5 7  2  6$
O secventa de modul $2$ ar fi cea reprezentata de sumele $8$ si $10$ cu indicii $7$ si $2$. Aceasta secventa este $(-6, -6, 9, 4, -3)$.

Observam ca cea mai mica diferenta intre termeni consecutivi e cea dintre $8$ si $7$ care au indicii $7$ si $5$, de unde obtinem ca subsecventa de modul minim este $(4, -3)$.
 
h2(#prob5). Problema 5 - USACO
 
Se da un sir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N (1 <= N <= 100 000)$ numere intregi ($1 <= a{~i~} <= 2 000$). Se cere sa se determine subsecventa $a[i..i + K - 1]$ cu media aritmetica a elementelor maxima ( $K >= F, 1 <= F <= N$).
 
h4. Exemplu
 
Pentru sirul $(6, 4, 2, 10, 3, 8, 5, 9, 4, 1)$ si $F = 6$ soluţia optima este $(10, 3, 8, 5, 9, 4)$, cu media $6.5$.
 
h3. Rezolvare
 
Fie $X$ un numar real. Daca obtinem sirul $b$ prin transformarea $b{~i~} = a{~i~} - X$, atunci toate subsecventele sirului $b$ vor avea valoarea mediei elementelor lor cu X mai mica decat valoarea subsecventelor corespunzatoare din sirul $a$. Daca subsecventa de suma maxima din $b$ are valoarea mai mare ca $0$, atunci si media ei va fi mai mare ca $0$. Rezulta astfel ca si media subsecventei corespunzatoare din sirul $a$ va fi mai mare decat $X$, deci media maxima a unei subsecvente din $a$ va fi mai mare ca $X$. Cand subsecventa de suma maxima din sirul $b$ are media mai mica decat zero, atunci orice subsecventa din sirul $a$ va avea media mai mica decat $X$. Iar in cazul in care subsecventa de suma maxima a sirului $b$ are valoarea egala cu zero, atunci subsecventa de medie maxima a sirului $a$ are media $X$. Astfel putem face o cautare binara pentru a determina valoarea $X$ a mediei maxime. Ne mai ramane sa determinam un algoritm eficient pentru gasirea subsecventei de suma maxima de lungime cel putin $F$.
O asemenea solutie este usor de facut urmarind una din ideile din prima problema: fie $best[i]$ subsecventa de suma maxima care se termina in $a[i]$. Evident $best[i] = max(a[i], best[i - 1] + a[i])$. Acum secventa de suma maxima ce se termina in $a[i]$ de lungime cel putin $F$ se gaseste ca $a[i] + a[i - 1] + .. + a[i - F + 2] + best[i - F + 1]$. Aceasta relatie poate fi calculata in $O(1)$ daca ne folosim de trucul sumelor partiale.
Astfel obtinem o solutie de complexitate $O(N log C)$, unde $C$ e valoarea maxima a lui $a{~i~}.
 

Observam ca cea mai mica diferenta intre termeni consecutivi e cea dintre $8$ si $7$ care au indicii $7$ si $5$, de unde obtinem ca subsecventa de modul minim este $(4, -3)$.