Информатика · объяснение и практика
Максимум списка: что хранить после каждого сравнения
Находим максимум неупорядоченного списка за один проход: выбираем начальное значение, сохраняем первую позицию при равенстве и проверяем отрицательные числа.

В теме Поиск и сортировка · Учебная карта
Главная мысль
Для непустого списка текущим максимумом сначала назначают первый элемент. Затем каждый следующий сравнивают с сохранённым кандидатом и заменяют его только при большем значении. После просмотра всех элементов кандидат равен максимуму списка. Чтобы сохранить первую позицию максимума, при равенстве обновление не выполняют.
Начальное число должно действительно быть в списке
Если начать с нуля, список отрицательных чисел может ошибочно получить максимум, которого в нём вообще нет. Поэтому безопасная инициализация для произвольных сравнимых чисел — первый элемент. Уже после неё есть простой факт: кандидат является наибольшим среди просмотренной части, пока состоящей из одного значения. При необходимости рядом сохраняют индекс этого элемента. В нашей записи индексы начинаются с нуля.
Пустой список требует отдельного договора. Можно запретить его для данной задачи, вернуть специальный результат или использовать явно заданное значение по умолчанию. Нельзя незаметно читать первый элемент отсутствующей последовательности. Встроенный Python max без default для пустого набора вызывает ValueError. Это не повод объявлять математический максимум пустого набора обычным нулём: поведение выбирают и сообщают до применения алгоритма.
Каждое сравнение сохраняет смысл кандидата
Пусть среди уже просмотренных элементов найден лучший кандидат. Новый элемент либо больше него, либо нет. Если больше, новый элемент становится наибольшим во всей расширенной части. Если не больше, прежний кандидат остаётся правильным. Это рассуждение повторяется до конца списка. Успех не зависит от того, где максимум находится: в начале, середине или последней позиции. Список сортировать для такой задачи не требуется.
Для первого максимального индекса используют строгое сравнение «больше». При сравнении «больше или равно» повторное такое же значение заменит сохранённую позицию и итогом станет последнее вхождение. Численный максимум в обоих вариантах одинаков, но ответ о позиции различается. Поэтому перед реализацией уточняют, требуется только значение, первая позиция, последняя позиция или все позиции. Одного слова «найти» для этих разных результатов недостаточно.
Пример
Найдём максимум и его первую позицию в списке [−8, −3, −11, −3].
Начальный кандидат −8 имеет индекс 0. На индексе 1 значение −3 больше, поэтому сохраняем −3 и индекс 1. Значение −11 не улучшает кандидат. Последнее −3 равно ему, поэтому строгая проверка не меняет позицию. Ответ: максимум −3, первая позиция 1.
Почему нельзя остановиться после первого улучшения
Линейный поиск известного значения может завершиться сразу после первого совпадения. При поиске максимума искомое число заранее неизвестно: следующий непросмотренный элемент способен оказаться ещё больше. Поэтому без дополнительной информации нужно пройти весь список. Для n элементов после начального назначения выполняется n − 1 сравнение. Одно улучшение кандидата не доказывает, что позднейших улучшений не будет.
Проверка включает список из одного элемента, полностью отрицательные данные, повторяющиеся максимумы и максимум в конце. Для единственного элемента сравнений нет, но ответ существует. Для нескольких одинаковых значений максимум совпадает с каждым из них, а правило строгого обновления сохраняет нулевой индекс. Такая проверка отделяет значение от позиции и выявляет ошибочную инициализацию лучше, чем несколько положительных возрастающих примеров подряд.
От чтения к действию
А теперь — вы
Частые вопросы
Нужно ли перед поиском максимума сортировать список?
Нет. Один полный проход сохраняет лучшего кандидата и не меняет порядок исходных данных.
Почему строгое сравнение сохраняет первую позицию?
Равное значение не обновляет индекс. Поэтому первое появление итогового максимума остаётся сохранённым до конца просмотра.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как линейный поиск обрабатывает найденный и отсутствующий элемент
Как линейный поиск проверяет элементы по порядку, возвращает первую подходящую позицию и обозначает отсутствие так, чтобы не спутать его с индексом ноль.
Открыть темуКак инвариант объясняет правильность накопления суммы
Как инвариант объясняет цикл накопления суммы: начальное состояние, сохранение свойства одним шагом и вывод после конечного числа итераций.
Открыть тему