Fişierul intrare/ieşire: | maxsecv.in, maxsecv.out | Sursă | Unirea2007 |
Autor | Daniel Pasaila | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 20096 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Maxsecv
Johnie are un vector binar de N elemente. El poate extrage o anumita subsecventa din vector, ramanand astfel cu un vector mai mic. Apoi, el poate insera subsecventa extrasa la orice pozitie din vectorul rezultat.
Se cere sa se afle lungimea maxima a unei subsecvente pline de 1 pe care o poate obtine Johnie daca efectueaza o singura operatie.
Date de intrare
Pe prima linie a fisierului maxsecv.in se afla N, dimensiunea vectorului. Urmeaza apoi pe urmatoarea linie N numere de 0 si 1, reprezentand elementele vectorului.
Date de iesire
Fisierul de iesire maxsecv.out trebuie sa contina un singur numar, reprezentand valoarea ceruta.
Restrictii
- 1 ≤ N ≤ 1 000 000
Exemplu
maxsecv.in | maxsecv.out |
---|---|
6 1 1 0 1 1 1 | 5 |
13 0 1 1 1 0 1 1 1 1 0 1 1 0 | 7 |
Explicatie
La primul exemplu Johnie poate muta subsecventa formata din ultimele 3 elemente ale vectorului la inceputul acestuia, obtinand o subsecventa formata din 5 de 1.
La al doilea exemplu Johnie poate selecta secventa de 4 de 1 din interiorul vectorului si o poate muta langa secventa de 3 de 1 de la inceput.