Clasa a IX-a · Șiruri de numere citite pe rândRead in English

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

În engleză: Longest run of equal elements

O(n)C++1748 de linii1 exemplu

Ideea

O secvență înseamnă elemente aflate pe poziții consecutive. lung este lungimea secvenței curente: crește când numărul nou este egal cu cel anterior și revine la 1 când este diferit. După fiecare pas actualizăm lungimea maximă și valoarea care o formează. Se afișează lungimea maximă și valoarea (prima, la egalitate).

Descrierea în engleză

A run means elements on consecutive positions. lung is the length of the current run: it grows when the new number equals the previous one and goes back to 1 when it differs. After every step we update the maximum length and the value that forms it. The maximum length and the value (the first one, on ties) are printed.

Complexitate
O(n)
Clasa
Clasa a IX-a (Grade 9)

Exemple

Exemplul 1

Intrare

10
1 1 2 2 2 3 2 2 2 2

Ieșire așteptată

4 2

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

cea-mai-lunga-secventa-de-egale.cpp
/*
 * Titlu: Cea mai lungă secvență de elemente egale
 * Clasa: 9
 * Capitol: Șiruri de numere citite pe rând
 * Descriere: O secvență înseamnă elemente aflate pe poziții consecutive.
 *            lung este lungimea secvenței curente: crește când numărul nou este
 *            egal cu cel anterior și revine la 1 când este diferit. După fiecare
 *            pas actualizăm lungimea maximă și valoarea care o formează.
 *            Se afișează lungimea maximă și valoarea (prima, la egalitate).
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 10
 * 1 1 2 2 2 3 2 2 2 2
 * Ieșire: 4 2
 */
#include <iostream>
using namespace std;

int main()
{
    int n, lung = 1, lungMax = 1;
    long long ant, x, valoare;
    cin >> n >> ant;
    valoare = ant;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        if (x == ant)
        {
            lung++;
        }
        else
        {
            lung = 1;
        }
        if (lung > lungMax)
        {
            lungMax = lung;
            valoare = x;
        }
        ant = x;
    }
    cout << lungMax << ' ' << valoare << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.