1. Идея

Нужно найти два значения в массиве:

• минимальный элемент;
• максимальный элемент.

Самый простой и правильный способ — пройти по массиву один раз и поддерживать два текущих ответа:

• mn — минимум среди уже просмотренных элементов;
• mx — максимум среди уже просмотренных элементов.

Сначала удобно присвоить обеим переменным первый элемент массива. После этого для каждого следующего числа:

• если оно меньше mn, обновляем минимум;
• если оно больше mx, обновляем максимум.

В конце выводим mn и mx.

2. Наблюдения

1. Перебирать все пары элементов не нужно.
   Для поиска минимума и максимума достаточно одного прохода по массиву.

2. Если инициализировать mn и mx первым элементом, не нужно придумывать специальные очень большие или очень маленькие значения.

3. Так как n >= 1, первый элемент точно существует, значит такая инициализация корректна.

4. После обработки первых i элементов:

   • mn хранит минимум на этом префиксе;
   • mx хранит максимум на этом префиксе.

Именно это позволяет получить ответ за линейное время.

3. Алгоритм

1. Считать число n.
2. Считать массив из n целых чисел.
3. Присвоить:
   • mn = a[0]
   • mx = a[0]
4. Пройти по массиву, начиная со второго элемента:
   • если a[i] < mn, то mn = a[i];
   • если a[i] > mx, то mx = a[i].
5. Вывести mn и mx.

4. Почему это работает

Докажем, что алгоритм действительно находит минимум и максимум массива.

После чтения первого элемента:

• mn = a[0] — это минимум среди первых 1 элемента;
• mx = a[0] — это максимум среди первых 1 элемента.

Теперь предположим, что после обработки элементов с индексами от 0 до i - 1 верно:

• mn равен минимуму среди a[0], a[1], ..., a[i - 1];
• mx равен максимуму среди a[0], a[1], ..., a[i - 1].

Рассмотрим следующий элемент a[i].

• Если a[i] < mn, значит новый минимум — это a[i], и мы обновляем mn.
• Иначе минимум не меняется.

То же самое для максимума:

• Если a[i] > mx, значит новый максимум — это a[i], и мы обновляем mx.
• Иначе максимум не меняется.

Значит после обработки a[i] переменные mn и mx снова правильно хранят минимум и максимум уже для первых i + 1 элементов.

По индукции после обработки всего массива:

• mn — минимум всего массива;
• mx — максимум всего массива.

Следовательно, алгоритм корректен.

5. Сложность

Пусть в массиве n элементов.

• Время работы: O(n), потому что массив просматривается один раз.
• Дополнительная память: O(1), если не считать память под сам массив.

В приведённых решениях массив считывается целиком, поэтому фактически используется O(n) памяти на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long mn = a[0];
    long long mx = a[0];

    for (int i = 1; i < n; i++) {
        if (a[i] < mn) {
            mn = a[i];
        }
        if (a[i] > mx) {
            mx = a[i];
        }
    }

    cout << mn << " " << mx << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

mn = a[0]
mx = a[0]

for i in range(1, n):
    if a[i] < mn:
        mn = a[i]
    if a[i] > mx:
        mx = a[i]

print(mn, mx)