1. Идея

Нужно найти среди n температур две величины:

• минимальную;
• максимальную.

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

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

Когда читаем очередное число, сравниваем его с mn и mx и при необходимости обновляем.

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

1. Если уже известны минимум и максимум для первых нескольких элементов, то для следующего элемента достаточно:

   • проверить, не меньше ли он текущего минимума;
   • проверить, не больше ли он текущего максимума.

2. Нет необходимости сортировать массив. Сортировка дала бы лишнюю работу, потому что для задачи нужны только два значения, а не полный порядок элементов.

3. Удобно взять первый элемент массива как начальные значения и для минимума, и для максимума:

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

   После этого можно начинать просмотр со второго элемента.

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

3. Алгоритм

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

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

Докажем, что после обработки всех элементов mn и mx действительно равны минимуму и максимуму всего массива.

Сначала после инициализации:

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

То есть для первого элемента всё верно: минимум и максимум среди одного числа — это само это число.

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

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

Рассмотрим элемент a[i].

• Если a[i] < mn, то новый минимум должен стать равным a[i], и алгоритм это делает.
• Если a[i] >= mn, то старый минимум остаётся правильным.

Аналогично:

• Если a[i] > mx, то новый максимум должен стать равным a[i], и алгоритм это делает.
• Если a[i] <= mx, то старый максимум остаётся правильным.

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

По индукции это верно после обработки всего массива. Следовательно, в конце алгоритм выводит правильные ответ: минимальную и максимальную температуру за день.

5. Сложность

• Время: O(n), потому что каждый элемент рассматривается ровно один раз.
• Память: 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)