
Problema interesanta Pbinfo – #4478 Nr max de zerouri
Cum să găsești cea mai lungă secvență de 1 într-un șir binar, schimbând cel mult k zerouri?
O problemă interesantă de algoritmică și optimizare – Soluție eficientă în C++
În acest articol, vom analiza o problemă frecvent întâlnită în competițiile de programare și interviurile tehnice: cum găsim cea mai lungă secvență de 1 într-un șir binar, permițând schimbarea a cel mult k zerouri în 1.
Această problemă poate fi rezolvată eficient cu ajutorul ferestrei glisante (sliding window), o tehnică foarte utilă pentru probleme de optimizare pe secvențe.
Tehnica „Sliding Window” (fereastră glisantă) este un algoritm eficient folosit pentru a găsi soluții la probleme care implică subsecvențe sau submulțimi dintr-un șir de date. Aceasta permite parcurgerea optimă a unei ferestre de lungime variabilă, fără a recalcula de la zero fiecare posibilitate, ceea ce reduce complexitatea algoritmică.

Ideea de bază a metodei „Sliding Window”
În loc să verificăm toate posibilele subsecvențe (ceea ce ar duce la o soluție ineficientă cu O(n^2), vom folosi doi indici, left și right, pentru a defini o fereastră care se mișcă prin șir.
Această fereastră se extinde și se restrânge dinamic în funcție de anumite condiții impuse de problemă.
Algoritmul metodei „Sliding Window”?
- Inițializăm doi indici:
left
(capătul stâng al ferestrei)right
(capătul drept al ferestrei)
- Extindem fereastra către dreapta (
right
crește)- Adăugăm elemente în fereastră.
- Dacă fereastra devine invalidă (ex. depășim un prag de valori permise), restrângem fereastra din stânga (
left
crește)- Eliminăm elemente pentru a readuce fereastra la o stare validă.
- În fiecare pas, actualizăm rezultatul optim (ex. lungimea maximă a unei subsecvențe valide).
În acest articol, îți voi explica cum să abordezi problema, cum să scrii un cod optimizat în C++ și de ce această soluție este eficientă.
Enunț
Avem un șir format din n valori binare (0 și 1) și un număr k, care reprezintă numărul maxim de zerouri pe care le putem schimba în 1. Trebuie să determinăm cea mai lungă secvență de 1 care poate fi obținută prin schimbarea a cel mult k zerouri.

Exemplu de intrare și ieșire
Exemplu 1
Intrare:
10 2
Ieșire:
1 0 0 1 1 0 1 0 1 16
Explicație:
Modificăm două zerouri astfel încât obținem cea mai lungă secvență continuă de 1. Secvența maximă posibilă este: 1 1 1 1 1 1 (6 elemente).
Rezolvarea problemei: Algoritmul „Sliding Window”
Această problemă poate fi rezolvată eficient folosind ferestre glisante (Sliding Window), o metodă care ne permite să analizăm segmentele unui șir fără a recalcula fiecare posibilitate de la zero.
Pașii algoritmului de rezolvare:
- Folosim doi indici:
left
(capătul stâng al ferestrei) șiright
(capătul drept). - Extindem fereastra spre dreapta (
right
) până când întâlnim mai mult dek
zerouri. - Dacă numărul de zerouri depășește
k
, restrângem fereastra (left
crește) pentru a reveni în limita permisă. - Păstrăm lungimea maximă a secvenței găsite.
Această metodă ne permite să parcurgem șirul într-o singură trecere, ceea ce face ca soluția să fie foarte eficientă.
Implementarea algoritmului folosind C++
Acum că am înțeles principiul, să vedem implementarea completă în C++:
#include <iostream>
using namespace std;
int maxSequence(int n, int k, int a[]) {
int left = 0, right = 0;
int zeroCount = 0, maxLen = 0;
while (right < n) {
if (a[right] == 0)
zeroCount++;
while (zeroCount > k) {
if (a[left] == 0)
zeroCount--;
left++;
}
maxLen = max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
int main() {
int n, k;
cin >> n >> k;
int v[n];
for (int i = 0; i < n; i++)
cin >> v[i];
cout << maxSequence(n, k, v) << endl;
return 0;
}
Explicația codului
- Inițializăm variabilele:
left = 0
→ marginea stângă a ferestrei.right = 0
→ marginea dreaptă a ferestrei.zeroCount = 0
→ numără câte zerouri avem în fereastră.maxLen = 0
→ reține cea mai lungă secvență validă.
- Extindem fereastra (cât timp
right < n
):- Dacă întâlnim un 0, creștem
zeroCount
. - Dacă
zeroCount > k
, mutămleft
spre dreapta pentru a elimina un 0.
- Dacă întâlnim un 0, creștem
- Actualizăm
maxLen
pentru fiecare fereastră validă. - La final, returnăm
maxLen
, adică lungimea maximă a secvenței de 1 obținute după modificări.
🚀 Complexitatea algoritmului
Această soluție are complexitate O(n) deoarece fiecare element este procesat cel mult o singură dată.
- Parcurgem șirul cu
right
o dată. - Deplasăm
left
cel mult o dată pentru fiecare element.
Prin urmare, avem un timp de rulare optim, potrivit și pentru valori mari ale lui n.
De ce această soluție este eficientă?
✔️ Nu reconstruim șirul de fiecare dată
✔️ Folosește o singură trecere prin date (O(n))
✔️ Nu necesită memorie suplimentară (O(1))
✔️ Ideal pentru probleme de optimizare pe secvențe
Alte variante de rezolvare
- Metodă brute-force (O(n^2))
- Testează toate secvențele posibile → ineficient pentru n mari.
- Utilizarea unui prefix-sum
- Stocăm prefixele și căutăm binar poziția optimă → mai complex de implementat.
Totuși, metoda „sliding window” rămâne abordarea optimă, fiind cea mai rapidă și ușor de înțeles.
Concluzie
Aceasta este o problemă clasică de optimizare pe secvențe, unde utilizarea tehnicii „sliding window” ne ajută să obținem o soluție eficientă în O(n).
Dacă ai întrebări sau vrei să vezi mai multe exemple de probleme similare, lasă un comentariu!