De ce contează?
Meteorologul vrea să știe cel mai lung șir de zile consecutive cu ploaie. Nu numără toate zilele cu ploaie — numără ziua curentă a blocului continuu și ține minte cel mai lung bloc văzut. Când apare soarele, contorul se resetează la zero.
Structura algoritmului
Menținem două variabile:
lung_cur— lungimea blocului activ (elementele consecutive care satisfac proprietatea)lung_max— cel mai lung bloc văzut până acum
La fiecare element nou:
- Dacă satisface proprietatea:
lung_cur++, actualizeazălung_max - Dacă nu: resetează
lung_cur = 0
Sir: 2 4 3 6 8 10 1 (proprietate: par)
lung_cur = 0, lung_max = 0
x=2: par → lung_cur=1, lung_max=1
x=4: par → lung_cur=2, lung_max=2
x=3: impar → lung_cur=0
x=6: par → lung_cur=1, lung_max=2
x=8: par → lung_cur=2, lung_max=2
x=10: par → lung_cur=3, lung_max=3
x=1: impar → lung_cur=0
Rezultat: 3Implementare C++
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("secvente.in");
ofstream fout("secvente.out");
int n;
fin >> n;
int lung_cur = 0, lung_max = 0;
for (int i = 0; i < n; i++) {
int x;
fin >> x;
if (x % 2 == 0) { // proprietatea: par
lung_cur++;
if (lung_cur > lung_max) lung_max = lung_cur;
} else {
lung_cur = 0; // reset la intrerupere
}
}
fout << lung_max << "\n";
return 0;
}Exemplu: 7 / 2 4 3 6 8 10 1 → 3
Varianta cu prev — secvențe de valori egale
Când proprietatea depinde de relația față de elementul anterior (de exemplu valori egale), citești primul element separat și pornești bucla de la i = 1:
fin >> prev;
int lung_cur = 1, lung_max = 1;
for (int i = 1; i < n; i++) {
int x; fin >> x;
if (x == prev) {
lung_cur++;
if (lung_cur > lung_max) lung_max = lung_cur;
} else {
lung_cur = 1; // noul bloc incepe cu x
}
prev = x;
}Actualizează lung_max în interiorul blocului valid, nu doar la resetare. Dacă șirul se termină în mijlocul celui mai lung bloc, nu mai treci prin ramura else — lung_max ar rămâne la valoarea mai mică.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Lungimea maximă a unui bloc | O(n) | O(1) |
Greșeala 1: Actualizezi lung_max doar la resetare (lung_cur = 0), în else. Dacă șirul se termină cu cel mai lung bloc, niciodată nu dai reset — lung_max rămâne la valoarea mai mică.
Greșeala 2: La resetare pui lung_cur = 1 (presupunând că noul element satisface proprietatea) fără să verifici. Dacă nu satisface, începi cu 1 în loc de 0.
Greșeala 3: Confunzi „cel mai lung bloc" cu „cel mai lung sufix" sau „numărul total de elemente cu proprietatea". Sunt trei lucruri diferite — citește enunțul cu atenție.