Grade 9 · Number sequences read one at a timeCitește în română
Longest run of equal elements
Original: Cea mai lungă secvență de elemente egale
The idea
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.
Original description (Romanian)
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).
- Complexity
- O(n)
- Grade
- Grade 9 (Clasa a IX-a)
Examples
Input
10 1 1 2 2 2 3 2 2 2 2
Expected output
4 2
The code
Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.
/*
* 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;
}
Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.