1. Идея

Нужно найти размах массива, то есть значение max - min.

Самый прямой способ: пройти по всем элементам массива и одновременно поддерживать:

• минимальный элемент mn,
• максимальный элемент mx.

После этого ответом будет mx - mn.

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

1. Размах зависит только от двух чисел: наименьшего и наибольшего в массиве.

2. Не нужно сортировать массив:

   • сортировка работает дольше,
   • для задачи достаточно одного прохода.

3. Так как a_i могут быть от -10^9 до 10^9, разность тоже может быть большой, поэтому в C++ безопасно использовать тип long long.

4. Если в массиве один элемент, то минимум и максимум совпадают, значит ответ равен 0.

5. Если все элементы одинаковы, то ответ тоже 0.

3. Алгоритм

1. Считать n.
2. Считать первый элемент массива.
3. Инициализировать:
   • mn = первый элемент,
   • mx = первый элемент.
4. Для каждого следующего элемента:
   • если он меньше mn, обновить mn,
   • если он больше mx, обновить mx.
5. Вывести mx - mn.

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

Во время прохода по массиву мы всегда храним:

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

Это верно в самом начале, потому что после чтения первого элемента и минимум, и максимум равны ему.

Дальше для каждого нового числа:

• если оно меньше текущего минимума, значит новый минимум найден;
• если оно больше текущего максимума, значит новый максимум найден;
• иначе минимум и максимум не меняются.

После обработки всех элементов:

• mn будет минимумом всего массива,
• mx будет максимумом всего массива.

По определению размах массива равен максимум - минимум, то есть mx - mn.

5. Сложность

• Время: O(n), потому что массив просматривается один раз.
• Память:
  • в C++ решении: O(1), так как храним только несколько переменных;
  • в Python решении из эталона: O(n), потому что считывается весь список.

6. Код на C++17

#include <iostream>
using namespace std;

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

    long long x;
    cin >> x;
    long long mn = x, mx = x;

    for (int i = 1; i < n; i++) {
        cin >> x;
        if (x < mn) mn = x;
        if (x > mx) mx = x;
    }

    cout << (mx - mn) << "\n";
    return 0;
}

7. Код на Python 3

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

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

for x in a[1:]:
    if x < mn:
        mn = x
    if x > mx:
        mx = x

print(mx - mn)