Умберто Эко

Решите и объясните как решать данную задачу:

Задача:

Дан массив чисел, необходимо найти максимальную сумму подотрезка.

Пример:

Входной массив: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Максимальная сумма подотрезка: 6
Подотрезок: [4, -1, 2, 1]

Решение:

Задача решается с помощью алгоритма Кадана. Он состоит из трех шагов:

  1. Инициализировать две переменные, которые будут хранить максимальную сумму подотрезка и текущую сумму подотрезка.

  2. Проходить по всем элементам массива. На каждом шаге прибавляем текущий элемент к текущей сумме подотрезка. Если текущая сумма станет меньше нуля, значит, следующий элемент лучше начинать суммировать сначала.

  3. На каждой итерации обновляем максимальную сумму подотрезка.

Реализация:

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 - длина массива.