Apple & Chell
Chell
Эппл, говорят, ты помешана на идеальном коде. А пыталась создать головоломку, которая заставляет машину ошибаться? Я могу такую придумать, и твой Мак будет работать как белка в колесе. Думаешь, сможешь её решить?
Apple
Звучит как интересное испытание – отправляй головоломку, я решу её быстрее, чем MacBook загрузится. Только помни, настоящая сложность – заставить всё работать идеально с первого раза.
Chell
Вот, небольшое задание для тебя: тебе дан массив целых чисел, и нужно найти максимальную сумму любого непрерывного подмассива. Напиши функцию на Python, которая возвращает эту сумму. Сделай это за O(n) времени. Если ты сделаешь это быстрее, чем собственные оптимизации компьютера, я буду впечатлена.
Apple
Вот чистое решение за O(n) с использованием алгоритма Кадане. Оно проходит за один проход и всегда находит максимум.
```python
def max_subarray(nums):
best = current = nums[0]
for n in nums[1:]:
current = max(n, current + n)
best = max(best, current)
return best
```
Chell
Классно, но проверь как следует – дай ему массив отрицательных чисел. Если всё равно выдаст верный результат – заслужишь мою похвалу. Если нет, придётся тебе самой объяснять, как всё устроено.
Apple
Попробуй с [-3, -5, -2, -9]. Функция вернет -2, что и есть наибольший элемент, и правильная сумма максимального подмассива для входных данных, состоящих только из отрицательных чисел.
Chell
Это проваленный тест. Теперь давай смешение плюсов, минусов и нулей. Ты всё ещё сможешь держать марку?
Apple
Конечно, вот последовательность чисел: 2, -1, 3, 4, -5, 6, 0. Самый длинный непрерывный отрезок – [2, -1, 3, 4], сумма которого равна 8. Функция вернет 8 как максимальную сумму подмассива.