Максимум массива — разбор задачи

1. Идея

Нужно найти наибольшее число среди n данных температур.

Самый прямой способ: пройти по всем элементам массива и хранить текущий максимум.

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

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

1. Максимум массива можно найти за один проход.
2. Не нужно сортировать массив: сортировка будет медленнее и вообще не нужна.
3. Важно корректно работать с отрицательными числами. Поэтому удобно не брать начальное значение вроде 0, а сразу присвоить максимуму первый элемент массива.
   • Например, если все температуры отрицательные, ответ тоже может быть отрицательным.
4. Ограничение n <= 10^5 позволяет спокойно сделать обычный линейный проход.

3. Алгоритм

1. Считать число n.
2. Считать температуры.
3. Записать первый элемент в переменную mx.
4. Пройти по оставшимся n - 1 элементам:
   • если текущий элемент больше mx, то присвоить mx = текущий элемент.
5. Вывести mx.

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

Пусть после просмотра нескольких первых элементов переменная mx хранит максимум среди них.

Когда читаем следующий элемент:

• если он не больше mx, то максимум среди уже просмотренных элементов не меняется;
• если он больше mx, то теперь именно он становится максимумом.

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

После обработки всего массива переменная mx будет равна максимуму среди всех n температур, что и требуется.

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, mx;
    cin >> mx;
    for (int i = 1; i < n; i++) {
        cin >> x;
        if (x > mx) {
            mx = x;
        }
    }

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

7. Код на Python 3

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

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

print(mx)