Решите и объясните как решать данную задачу:
Задача:
Дан массив чисел, необходимо найти максимальную сумму подотрезка.
Пример:
Входной массив: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Максимальная сумма подотрезка: 6
Подотрезок: [4, -1, 2, 1]
Решение:
Задача решается с помощью алгоритма Кадана. Он состоит из трех шагов:
-
Инициализировать две переменные, которые будут хранить максимальную сумму подотрезка и текущую сумму подотрезка.
-
Проходить по всем элементам массива. На каждом шаге прибавляем текущий элемент к текущей сумме подотрезка. Если текущая сумма станет меньше нуля, значит, следующий элемент лучше начинать суммировать сначала.
-
На каждой итерации обновляем максимальную сумму подотрезка.
Реализация:
def max_subarray(arr):
max_so_far = arr[0] # максимальная сумма подотрезка
curr_max = arr[0] # текущая сумма подотрезка
for i in range(1, len(arr)):
curr_max = max(arr[i], curr_max + arr[i])
max_so_far = max(max_so_far, curr_max)
return max_so_far
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Максимальная сумма подотрезка:", max_subarray(arr))
Результат:
Максимальная сумма подотрезка: 6
Алгоритм работает за линейное время O(n), где n - длина массива.