Алгоритм Кадане и его доказательство — задача о максимальной/минимальной сумме подмассива

Описание: В этом видео вы получите оптимальное решение задачи на максимальную/минимальную сумму подмассива: алгоритм Кадане. Задача проста. Дан массив целых чисел, например, [-1, 1, 3, -2], и нужно найти подмассивы с максимально и минимально возможными суммами (в данном примере: max=[1, 3], min=[-2]). Алгоритм Кадане решает эту задачу с приемлемой временной сложностью O(n) и сложностью памяти O(1). Разновидностью этой задачи является поиск подмассива с максимальной/минимальной суммой, содержащего не менее k элементов. Для её решения можно использовать слегка изменённую версию алгоритма Кадане. Наконец, мы докажем корректность алгоритмов Кадане.

Если все целые числа в массиве положительные, можно использовать гораздо более простой метод скользящих окон. Для массивов с отрицательными числами можно изменить его так, чтобы все числа были положительными, а затем применить метод скользящего окна, но это требует дополнительной обработки; следовательно, это не оптимальное решение. У меня есть отдельное видео, подробно обсуждающее метод скользящего окна с различными примерами вопросов, ссылку на которое вы найдете ниже.

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

В видео вы найдёте решения следующих задач, а также их временную и пространственную сложность:
Средняя сложность: Алгоритм Кадане: Для заданного массива целых чисел найдите подмассив с максимально/минимальной возможной суммой.
Средняя сложность: Скользящее окно в алгоритме Кадане: Для заданного массива целых чисел найдите подмассив с максимально/минимальной возможной суммой, содержащий не менее k элементов.
Сложный уровень: Докажите алгоритм Кадане: Докажите корректность алгоритма Кадане.

Код решения к примерам доступен по ссылке:
https://github.com/soygul/QuanticDev/...

Если вы можете прочитать версию этого видео в формате статьи по ссылке:
http://quanticdev.com/algorithms/dyna...

Моё видео о методе скользящего окна, которое можно применить в схожих ситуациях:
   • Sliding Window Technique + 4 Questions - A...  

Мой плейлист «Алгоритмы» для всех остальных вопросов и ответов по алгоритмам:
   • Algorithms  

- - - - - - - - - - -
  / quanticdev  
  / quantic_dev  
https://quanticdev.com