Модуль: (Python) Оператор цикла for. Типовые задачи


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

☰ Теория

Задача

Дано N чисел. Найти второй по величине максимальный элемент последовательности.

Данная задача допускает два толкования.
Например, если нам дан набор чисел: \(10\ 15\ 20\ 35\ 14\ 35\ 10\), то каким должен быть ответ?
Под "вторым по величине максимальным элементом" или просто "вторым максимумом", можно понимать:
1) значение, которое стояло бы на предпоследнем месте, если бы мы все значения расставили (отсортировали) по неубыванию (каждый следующий больше или равен предыдущему). Тогда для рассмотренного набора чисел ответом будет значение 35;
2) значение элемента, больше которого только максимальный. Тогда ответ - 20.
Если в наборе чисел только один максимальный элемент (все остальные меньше), то оба толкования совпадают, и ответ будет одинаковый для обоих случаев, иначе - ответ будет разный.

Рассмотрим первый случай (алгоритм будем записывать на псевдокоде).
Для нахождения ответа будем использовать две переменные:
1) максимум1 - максимальное значение (первый максимум);
2) максимум2 - второй максимум (наш ответ).

Если диапазон изменения значений известен, то в качестве начальных значений принимаем число, которое заведомо меньше нижней границы диапазона (например, при диапазоне от -1000 до 1000 - берем число -1001)
Если диапазон значений неизвестен, то можно первые два вводимых числа записать в начальные значения переменных максимум1 и максимум2, а затем сравнить эти две переменных.
ввод N //количество чисел
ввод a, б
максимум1 = а
максимум2 = б
если б > а, то
    максимум1 = б
    максимум2 = а

Далее рассматриваем все остальные элементы (первые 2 уже просмотрели, значит начинать будем с 3го)
нц для i от 3 до n
    ввод а
    если а > максимум1 //встретилось значение большее максимума1
      то 
        максимум2 = максимум1 //бывший первый максимум станет вторым
        максимум1 = а  //первым максимумом станет новый элемент
      иначе
        //очередной элемент не больше максимум1
        //его необходимо сравнить со значением максимум2
        если а > максимум 2
          то
            максимум2 = а  //принимаем его в качестве нового значения максимум2
                           // максимум1 в этом случае не меняется
        все
    все
кц

Попробуйте реализовать данный алгоритм самостоятельно.

Дано N целых чисел. Найти второй по величине максимальный элемент последовательности (элемент, который бы стоял предпоследним, если бы входные данные отсортировали по неубыванию).

Входные данные
В первой строке задается число N (\(2<=N<=10^4\)). Далее идут N строк, в каждой строке по одному целому числу, не превышающему 105 по модулю. 

Выходные данные
Выведите второй максимальный элемент.

 

Примеры
Входные данные Выходные данные
1 7
10
15
20
35
14
35
10
35
2 5
10
5
7
11
9
10

Напишите программу
Auto
       

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64799
Free Pascal24
C#3
Java4
Python1566
PascalABC5
Комментарий учителя

Foxford Lectarium.ru