Светильники Вилед

Дана последовательность целых чисел. Найти отрезок этой последовательности с максимальной суммой.

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

Для решения этой задачи существует несколько алгоритмов, но наиболее эффективный из них - это алгоритм Кадана.

Алгоритм Кадана

Алгоритм Кадана заключается в следующем:

  1. Инициализировать две переменные: max_so_far и max_ending_here, обе равны нулю.
  2. Проходя по последовательности чисел, для каждого нового числа x:
    • Прибавить x к max_ending_here.
    • Если max_ending_here стало отрицательным, значит, текущий отрезок закончился и следует начать новый. В таком случае значение max_ending_here следует обнулить.
    • Если max_ending_here стало больше, чем max_so_far, то max_so_far следует обновить значением max_ending_here.
  3. После того, как проход по последовательности окончен, max_so_far будет равно сумме элементов максимального по сумме отрезка последовательности.

Реализация на Python

Вот пример реализации алгоритма Кадана на языке Python:

def max_subarray_sum(arr):
    max_so_far = max_ending_here = 0
    for x in arr:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

В этом примере функция max_subarray_sum принимает на вход список целых чисел arr и возвращает максимальную сумму элементов некоторого отрезка этого списка.

Примеры использования

Вот несколько примеров использования функции max_subarray_sum:

>>> max_subarray_sum([1, -2, 3, -4, 5])
5
>>> max_subarray_sum([-2, -3, 4, -1, -2, 1, 5, -3])
7
>>> max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
6

В первом примере максимальная сумма элементов на отрезке равна 5 и достигается на отрезке [3, -4, 5].

Во втором примере максимальная сумма элементов на отрезке равна 7 и достигается на отрезке [4, -1, -2, 1, 5].

В третьем примере максимальная сумма элементов на отрезке равна 6 и достигается на отрезке [4, -1, 2, 1].