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.

maximul-si-pozitiile-lui.cpp
/*
 * 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.