Cea mai lungă secvență de elemente egale în C++

Pentru 4 4 2 2 2 4, cea mai lungă secvență de elemente egale are lungimea 3 și începe pe poziția 3, dacă pozițiile se numără de la 1. Cele trei apariții ale lui 4 nu formează o secvență, fiind separate de alte valori.

Cerință precisă

Citim 1 ≤ n ≤ 1000 și n numere întregi. Afișăm poziția de început și lungimea celei mai lungi secvențe constante. La egalitate de lungime alegem secvența care începe prima. În cod folosim indici 0..n-1; numai la afișare adăugăm 1. Tabloul are capacitatea 1000, iar n reprezintă dimensiunea logică.

Vectorul 4, 4, 2, 2, 2, 4 are grupul maxim de trei valori egale pe pozițiile 3, 4 și 5.Mărește schema ↗

Starea parcurgerii

La indicele i, lung este lungimea secvenței constante care se termină exact acolo. Dacă a[i] coincide cu vecinul din stânga, prelungim secvența. Altfel, începem una nouă, de lungime 1, la i. Variabilele best și bestStart rețin cea mai bună secvență întâlnită.

Pornim de la primul element, care formează singur o secvență validă. De aceea bucla începe cu i=1, iar accesul a[i-1] rămâne valid. Actualizăm rezultatul imediat după fiecare pas, inclusiv după ultimul element. Nu este nevoie de un element fictiv la capăt.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1000];
    for (int i = 0; i < n; ++i) cin >> a[i];
    int lung = 1, best = 1, start = 0, bestStart = 0;
    for (int i = 1; i < n; ++i) {
        if (a[i] == a[i-1]) ++lung;
        else { lung = 1; start = i; }
        if (lung > best) { best = lung; bestStart = start; }
    }
    cout << bestStart + 1 << ' ' << best << '\n';
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int lung = 1, best = 1, start = 0, bestStart = 0;
    for (int i = 1; i < n; ++i) {
        if (a[i] == a[i-1]) ++lung;
        else { lung = 1; start = i; }
        if (lung > best) { best = lung; bestStart = start; }
    }
    cout << bestStart + 1 << ' ' << best << '\n';
}

Exemplu de egalitate

Pentru 5 5 1 1, lungimile succesive sunt 1, 2, 1, 2. Când găsim a doua secvență de lungime 2, condiția lung > best este falsă. Păstrăm începutul primei, deci rezultatul este 1 2. Dacă problema cere ultima secvență maximă, schimbarea trebuie făcută intenționat în >=.

Algoritmul este O(n) în timp și folosește O(1) memorie suplimentară față de vector. Nu sortăm: sortarea ar reuni valori care nu erau vecine și ar distruge răspunsul la cerința inițială.

Exersează

• Pentru un singur element, răspunsul este 1 1.
• Pentru 3 3 3 3, răspunsul este 1 4.
• Pentru 1 2 2 2, răspunsul este 2 3; acesta verifică secvența care ajunge la capăt.
• Pentru 1 2 3, răspunsul este 1 1, conform regulii de departajare.

Extinde problema pentru secvențe strict crescătoare. Înlocuiește egalitatea dintre vecini cu relația potrivită, dar păstrează sensul variabilelor și politica de departajare. Încearcă apoi să numeri câte secvențe constante maximale există: pentru 1 1 2 2 1, sunt trei.

Leagă această tehnică de secvențe și intervale, frecvențe, care ignoră vecinătatea și actualizarea unui rezultat optim.

Întrebări frecvente

Care este diferența dintre o secvență constantă și frecvența unei valori?

O secvență constantă conține elemente egale aflate pe poziții consecutive. Frecvența numără toate aparițiile unei valori, inclusiv cele separate. În 4 4 2 2 2 4, secvența maximă are lungimea 3 și valoarea 2.

Cum aleg între două secvențe constante de aceeași lungime?

În această lecție se alege prima. Actualizează rezultatul numai când lungimea curentă depășește strict maximul; actualizarea și la egalitate ar păstra o secvență ulterioară.

Ce se întâmplă dacă vectorul are un singur element?

Cea mai lungă secvență începe pe poziția 1 și are lungimea 1. Acest caz verifică inițializarea, deoarece nu există o pereche de vecini pe care să o compari.