Второй максимум

Второй максимум

Дан массив из \(n\) чисел. Найдите второе по величине различное значение. Гарантируется, что различных значений хотя бы два.

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

В первой строке \(n\) (\(2 \le n \le 50\)). Во второй строке \(n\) целых чисел.

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

Одно число — второе по величине среди различных значений.

Пример

Вход:

5
1 3 3 2 5

Выход:

3

Различные значения: 1, 2, 3, 5. Максимум — 5, второй — 3.

Ключевое наблюдение: «второй максимум» считается среди различных значений, поэтому повторы максимума не должны «съедать» ответ. Достаточно в одном проходе поддерживать два разных числа: mx1 (самое большое) и mx2 (второе по величине, но не равное mx1).

Почему работает: при просмотре очередного x есть всего три ситуации — он больше текущего максимума, он между первым и вторым, или он не улучшает ответ. Мы обновляем только эти две переменные, и после конца прохода mx2 уже является вторым по величине среди всех просмотренных значений.

План:

• Инициализируйте mx1 и mx2 очень маленькими значениями (например, float('-inf')).
• Для каждого числа x из массива:
• если x > mx1, то сдвиньте: mx2 = mx1, mx1 = x;
• иначе если mx1 > x > mx2, то обновите mx2 = x.
• Выведите mx2.

Мини-сниппет логики обновления:

• if x > mx1: mx2, mx1 = mx1, x
• elif mx1 > x > mx2: mx2 = x

Сложность: O(n) по времени и O(1) по памяти.

Частая ошибка: проверять x != mx1 вместо строгого mx1 > x во второй ветке — это может случайно принять число больше mx1 (если порядок условий неверный) или неправильно обработать повторы.