В этой статье мы обсудим, как алгоритм может превратить кажущуюся на первый взгляд сложную проблему в довольно простую. Алгоритм Кадане особенно часто используется для поиска подмассива максимальной суммы. Сейчас этот термин может показаться вам совершенно незнакомым, если вы не изучаете информатику или математику, поэтому давайте сначала разберемся с формулировкой задачи.

Что такое массив?

По сути, в программировании массив — это тип структуры данных или, проще говоря, способ хранения данных в памяти. Он используется для хранения данных одного типа (например, всех чисел, всего текста и т. д.) в смежных ячейках памяти. Он используется для хранения списков данных одного типа. Например,

На изображении выше у нас есть массив (или список для простоты) элементов целочисленного типа. Цифры под прямоугольниками — это индексы, используемые для адресации элемента. В большинстве языков программирования принято начинать индексацию с 0.

Что такое подмассив?

Теперь подмассив — это не что иное, как часть массива, состоящая только из смежных элементов. Например, в массиве, который мы использовали выше, элементы от индекса 2 до 5 образуют подмассив или элементы от индекса 4 до 6.

Задача максимальной суммы подмассива

Используя некоторые основные математические операции, мы можем узнать, что общее количество подмассивов в массиве длины n равно n*(n+1)/2. Теперь постановка задачи состоит в том, чтобы найти максимальную сумму, которую может иметь любой подмассив.

Например, если массив равен [-2,1,-3,4,-1,2,1,-5,4], подмассив [4,-1,2,1] имеет наибольшую сумму 6.

Подход грубой силы для решения этой проблемы состоит в том, чтобы найти все подмассивы и проверить, какой из них имеет максимальную сумму. Очевидно, что это правильный, но не оптимальный подход. Итак, как мы можем сделать лучше?

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

Теперь, чтобы сократить общее время вычислений и получить более оптимальное решение, мы выполним указанные шаги:

  1. Начиная с первого элемента, посетите каждый элемент массива один раз и сохраните 2 значения.

max_sum_ending_here: максимальная возможная сумма подмассива для любого подмассива, заканчивающегося текущим элементом.

max_sum_so_far: максимальная возможная сумма подмассива для любого подмассива, заканчивающегося на текущем элементе или перед ним.

Чтобы запустить процесс, мы инициализируем max_sum_ending_here как 0, а max_sum_so_far как -inf(минимальное целочисленное значение, возможное в используемом нами языке.

2. Теперь на каждой итерации мы добавляем текущий элемент в max_sum_ending_here и проверяем, больше ли он, чем max_sum_so_far. Если да, мы заменяем max_sum_so_far на max_sum_ending_here.

3. Теперь еще один шаг, который мы добавляем для оптимизации процесса, — это проверка того, меньше ли max_sum_ending_here 0 после описанного выше процесса. Если да, мы заменяем его на 0, тем самым говоря, что включение текущего элемента в любой подмассив только уменьшит сумму, поскольку максимально возможная сумма любого подмассива, заканчивающегося текущим элементом, равна 0. Следовательно, мы не будем включать текущий элемент ни в какой подмассив, включая элементы после него.

В конце процесса max_sum_so_far будет нашим требуемым ответом, так как это максимальная возможная сумма подмассива до последнего элемента, т. е. весь массив.

Вышеописанный процесс можно резюмировать следующим образом:

Initialize:
    max_so_far = INT_MIN
    max_ending_here = 0

Loop for each element of the array

  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
  (c) if(max_ending_here < 0)
            max_ending_here = 0
return max_so_far

Примечание. Если в массиве есть только отрицательные целые числа, то добавление любого элемента к другому элементу только уменьшит нашу сумму. Таким образом, в этом крайнем случае нашим ответом будет просто самое большое число в массиве (или наименьшее число по величине).

Хороший пробный запуск можно увидеть здесь:

Следовательно, подмассив [3,-1,2] имеет максимальную сумму, т. е. 4.

ОБЗОР

Алгоритм Кадане — хороший пример подхода динамического программирования к решению задач. В этом подходе мы делим большую проблему на меньшие перекрывающиеся подзадачи. Например, чтобы найти подмассив максимальной суммы, заканчивающийся в определенной позиции, мы используем подмассив максимальной суммы, заканчивающийся в предыдущей позиции. и это делается рекурсивно.

Главной особенностью этого алгоритма является жадный подход, т. е. попытка сделать наиболее оптимальный выбор на каждой итерации (сохранить текущий элемент или удалить его, установив max_sum_ending_here обратно в 0) и, таким образом, достичь глобально оптимальное решение в конце.

В ЗАКЛЮЧЕНИЕ..

Надеюсь, вам, ребята, понравилась эта статья, и я смог передать что-то интересное читателям. До тех пор не стесняйтесь обращаться ко мне через комментарии или по адресу [email protected], чтобы оставить отзыв или указать на любые технические или письменные ошибки, если вы так считаете.

Если вам понравилась эта статья, не стесняйтесь хлопать в ладоши. Это будет мотивировать меня писать больше.

СПАСИБО ЗА ПРОЧТЕНИЕ!!!!