• 0736-069-356
  • admin@lanteam-solutions.com
  • Cluj, Romania
Blog
Problema interesanta Pbinfo – #4478  Nr max de zerouri

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”?

  1. Inițializăm doi indici:
    • left (capătul stâng al ferestrei)
    • right (capătul drept al ferestrei)
  2. Extindem fereastra către dreapta (right crește)
    • Adăugăm elemente în fereastră.
  3. 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ă.
  4. Î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.


pb4478pbinfo

Exemplu de intrare și ieșire

Exemplu 1

Intrare:

10 2
1 0 0 1 1 0 1 0 1 1
Ieșire: 6
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:

  1. Folosim doi indici: left (capătul stâng al ferestrei) și right (capătul drept).
  2. Extindem fereastra spre dreapta (right) până când întâlnim mai mult de k zerouri.
  3. Dacă numărul de zerouri depășește k, restrângem fereastra (left crește) pentru a reveni în limita permisă.
  4. 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

  1. 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ă.
  2. Extindem fereastra (cât timp right < n):
    • Dacă întâlnim un 0, creștem zeroCount.
    • Dacă zeroCount > k, mutăm left spre dreapta pentru a elimina un 0.
  3. Actualizăm maxLen pentru fiecare fereastră validă.
  4. 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

  1. Metodă brute-force (O(n^2))
    • Testează toate secvențele posibile → ineficient pentru n mari.
  2. 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!

Lasă un răspuns