Функция начинает с первого элемента и заменяет max_val каждый раз, когда встречает большее значение. После прохода max_val содержит максимум. Для непустого списка сравнимых чисел без NaN алгоритм корректен; пустой список вызывает IndexError. Время — O(n), дополнительная память — O(1).
Как функция find_max на Python находит максимальный элемент массива?
Разбираем поиск максимума одним проходом без изменения кода функции: инвариант, отрицательные числа, пустой список и оценка сложности.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Функция получает массив чисел и возвращает наибольший элемент. Разберите её работу, не изменяя тело функции. Несмотря на размещение исходника в разделе frontend, код написан на Python.
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
Почему это работает
Вначале кандидатом в максимум становится первый элемент. После рассмотрения каждого очередного числа max_val хранит наибольшее из уже просмотренных значений. Если новое число больше, кандидат обновляется; иначе прежний максимум остаётся правильным. После прохода просмотрены все элементы, поэтому возвращается максимум всего списка.
Первый элемент сравнивается сам с собой. Для обычных чисел это лишняя, но безвредная проверка; менять код ради неё условие не требует.
print(find_max([3, 8, 2, 8])) # 8
print(find_max([-7, -2, -9])) # -2
print(find_max([5])) # 5
Инициализация первым элементом, а не нулём, позволяет правильно работать со списком только из отрицательных чисел. Повторение максимального значения тоже не мешает: нужно вернуть значение, а не индекс его последнего появления.
Границы применимости
Вход должен быть непустым: для [] обращение arr[0] вызывает IndexError. Поскольку тело менять нельзя, проверку пустого входа при необходимости выполняет вызывающий код. Смешивание несравнимых типов может привести к TypeError. Для float('nan') обычный порядок сравнения не выполняется, поэтому поведение с NaN нужно оговаривать отдельно.
Для n обычных числовых элементов выполняется один проход: O(n) времени и O(1) дополнительной памяти. Список не сортируется и не изменяется.