Максимум массива

Максимум массива

Дан массив из \(n\) чисел. Найдите наибольшее.

Входные данные

В первой строке \(n\) (\(1 \le n \le 100\)). Во второй строке \(n\) целых чисел (\(-10^6 \le a_i \le 10^6\)).

Выходные данные

Одно число — максимум массива.

Пример

Вход:

3
1 5 2

Выход:

5

Ключевое наблюдение: максимум среди первых k элементов можно знать, не пересматривая их заново — достаточно хранить одно число mx, равное текущему максимуму. Когда читаем следующий элемент x, новый максимум — это либо старый mx, либо x, если он больше. Так мы сводим задачу к одному проходу.

Почему это работает: максимум множества не зависит от порядка. Если мы всегда держим максимум уже просмотренных чисел, то после просмотра всех n элементов этот максимум и будет ответом.

План решения:

• Считай n.
• Считай n чисел (списком или по одному).
• Инициализируй mx первым числом массива.
• Для каждого следующего числа x:
• если x > mx, то обнови mx = x (или короче: mx = max(mx, x)).
• Выведи mx.

Сложность: O(n) по времени и O(1) по дополнительной памяти (если обрабатываешь числа по одному; если читаешь в список — память O(n), но при n до 100 это не критично).

Частая ошибка: инициализировать mx нулём. Тогда для массива из одних отрицательных чисел ответ получится неверным. Надёжно начинать с первого элемента массива.