Дан список чисел nums. Напишите функцию find_max(nums), которая возвращает максимальный элемент, не используя встроенную функцию max(). Что вернуть для пустого списка?
Линейный проход за O(n)
Алгоритм: предполагаем, что первый элемент максимальный, затем сравниваем с остальными.
def find_max(nums: list[int]) -> int:
if not nums:
raise ValueError("Список пуст")
current_max = nums[0]
for x in nums[1:]:
if x > current_max:
current_max = x
return current_max
print(find_max([3, 1, 4, 1, 5, 9, 2, 6])) # 9
print(find_max([-7, -2, -10])) # -2
Для пустого списка выбрасываем исключение, так как максимума не существует. Альтернативно — возвращать None и обрабатывать у вызывающего.
Сложность: $O(n)$, дополнительная память $O(1)$. Меньше нельзя — нужно посмотреть на каждый элемент хотя бы раз.
Razbery — про разбор, не про списывание. Объяснение обязательно.