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
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
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.
/*
* 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.