Grade 9 · One-dimensional arrays (vectors)Citește în română
The maximum and the positions where it appears
Original: Maximul și pozițiile pe care apare
O(n)C++1750 lines1 example
The idea
Unlike a sequence read one value at a time, an array can be traversed several times: in the first pass we find the maximum, in the second we print every position where it appears.
Original description (Romanian)
Spre deosebire de un șir citit pe rând, un vector poate fi parcurs de mai multe ori: la prima parcurgere aflăm maximul, la a doua afișăm toate pozițiile pe care apare.
- Complexity
- O(n)
- Grade
- Grade 9 (Clasa a IX-a)
Examples
Example 1
Input
6 4 9 2 9 1 9
Expected output
9 2 4 6
The code
Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.
/*
* Titlu: Maximul și pozițiile pe care apare
* Clasa: 9
* Capitol: Tablouri unidimensionale (vectori)
* Descriere: Spre deosebire de un șir citit pe rând, un vector poate fi
* parcurs de mai multe ori: la prima parcurgere aflăm maximul, la a
* doua afișăm toate pozițiile pe care apare.
* Complexitate: O(n)
*
* Exemplu
* Intrare:
* 6
* 4 9 2 9 1 9
* Ieșire:
* 9
* 2 4 6
*/
#include <iostream>
using namespace std;
int v[1001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> v[i];
}
int maxim = v[1];
for (int i = 2; i <= n; i++)
{
if (v[i] > maxim)
{
maxim = v[i];
}
}
cout << maxim << '\n';
for (int i = 1; i <= n; i++)
{
if (v[i] == maxim)
{
cout << i << ' ';
}
}
cout << '\n';
return 0;
}
Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.