h2. secv4

Deoarece logaritmul unui produs de numere este egal cu suma logaritmilor fiecarui numar din produs, si in ipoteza ca toate numerele din sir sunt pozitive, logaritmam fiecare numar si notam cu $S{~i~}$ suma primilor $i$ logaritmi. Astfel, pentru a afla secventa de produs maxim care se termina pe pozitia $i$, este suficient sa determinam, pentru $k$ intre $i-y$ si $i-x$ care este $S{~k~}$ minim (astfel, $S{~i~} - S{~k~}$ va fi maxim, deci si produsul maxim, iar secventa va incepe pe pozitia $k+1$). Putem folosi un arbore de intervale si obtinem un algoritm $O(NlogN)$, sau o coada prin care scoatem elementele prin ambele parti (structura de date numita deque - double ended queue), obtinand complexitatea $O(N)$. Daca exista si numere negative, in momentul logaritmarii numerelor negative logaritmam opusul lor. Aplicand procedeul descris mai sus, stim sigur la final ca produsul obtinut are modulul maxim. Pentru a fi cu adevarat maxim (deci pozitiv), notam cu $semn{~i~}$ semnul produsului primelor $i$ numere. Ca secventa {$<j+1, i>$} sa aiba produs maxim trebuie in plus $semn{~i~} = semn{~j~}$. Vom retine doua deque-uri, unul pentru {$+$} si unul pt {$-$}, conform vectorului semn. Astfel, in final, suntem siguri ca produsul are semnul {$+$} si, cum are si modulul maxim, are valoarea maxima ceruta.

Deoarece logaritmul unui produs de numere este egal cu suma logaritmilor fiecarui numar din produs, si in ipoteza ca toate numerele din sir sunt pozitive, logaritmam fiecare numar si notam cu $S{~i~}$ suma primilor $i$ logaritmi. Astfel, pentru a afla secventa de produs maxim care se termina pe pozitia $i$, este suficient sa determinam, pentru $k$ intre $i-y$ si $i-x$ care este $S{~k~}$ minim (astfel, $S{~i~} - S{~k~}$ va fi maxim, deci si produsul maxim, iar secventa va incepe pe pozitia $k+1$). Putem folosi un arbore de intervale si obtinem un algoritm $O(NlogN)$, sau o coada prin care scoatem elementele prin ambele parti (structura de date numita deque - double ended queue), obtinand complexitatea $O(N)$. Daca exista si numere negative, in momentul logaritmarii numerelor negative logaritmam opusul lor. Aplicand procedeul descris mai sus, stim sigur la final ca produsul obtinut are modulul maxim. Pentru a fi cu adevarat maxim (deci pozitiv), notam cu $semn{~i~}$ semnul produsului primelor $i$ numere. Ca secventa $<j+1, i>$ sa aiba produs maxim trebuie in plus $semn{~i~} = semn{~j~}$. Vom retine doua deque-uri, unul pentru $+$ si unul pt $-$, conform vectorului semn. Astfel, in final, suntem siguri ca produsul are semnul $+$ si, cum are si modulul maxim, are valoarea maxima ceruta.

h2. parcare