Аспект динамического программирования в алгоритме Кадане

Согласно этому определению перекрывающихся подзадач рекурсивная формулировка алгоритма Кадане (f[i] = max(f[i - 1] + a[i], a[i])) не демонстрирует это свойство. Каждая подзадача будет вычисляться только один раз в наивной рекурсивной реализации.

Однако он демонстрирует оптимальную подструктуру в соответствии с его определением, которое здесь: мы используем решение меньших подзадач, чтобы найти решение данной проблемы (f[i] использует f[i - 1]).

Рассмотрим определение динамического программирования, которое здесь:

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

Идея динамического программирования довольно проста. В общем, чтобы решить данную проблему, нам нужно решить разные части проблемы (подзадачи), а затем объединить решения подзадач для достижения общего решения. Часто при использовании более наивного метода многие подзадачи генерируются и решаются много раз. Подход динамического программирования стремится решить каждую подзадачу только один раз, что сокращает количество вычислений.

Это оставляет место для интерпретации относительно того, может ли алгоритм Кадана считаться алгоритмом DP: он решает проблему, разбивая ее на более простые подзадачи, но его основной рекурсивный подход не генерирует перекрывающиеся подзадачи, для чего предназначен DP. обрабатывать эффективно - так что это выведет его за рамки специализации DP.

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

Поэтому я бы сказал, что это не алгоритм DP, а просто жадный и / или рекурсивный, в зависимости от реализации. Я бы назвал его жадным с алгоритмической точки зрения по причинам, перечисленным выше, но объективно я бы счел и другие интерпретации столь же верными.

Обратите внимание, что я получил свое объяснение из этого ответа. Он демонстрирует, как алгоритм Кадане можно рассматривать как алгоритм DP, который имеет перекрывающиеся подзадачи.

Выявление подзадач и повторяющихся отношений

Представьте, что у нас есть массив a, из которого мы хотим получить максимальный подмассив. Чтобы определить максимальный подмассив, который заканчивается индексом i, выполняется следующее рекурсивное отношение:

max_subarray_to(i) = max(max_subarray_to(i - 1) + a[i], a[i])

Чтобы получить максимальный подмассив a, нам нужно вычислить max_subarray_to() для каждого индекса i в a, а затем взять из него max():

max_subarray = max( for i=1 to n max_subarray_to(i) )

Пример

Теперь предположим, что у нас есть массив [10, -12, 11, 9], из которого мы хотим получить максимальный подмассив. Это будет работа, необходимая для запуска алгоритма Кадане:

result = max(max_subarray_to(0), max_subarray_to(1), max_subarray_to(2), max_subarray_to(3))

max_subarray_to(0) = 10  # base case
max_subarray_to(1) = max(max_subarray_to(0) + (-12), -12)
max_subarray_to(2) = max(max_subarray_to(1) + 11, 11)
max_subarray_to(3) = max(max_subarray_to(2) + 9, 49)

Как видите, max_subarray_to() оценивается дважды для каждого i, кроме последнего индекса 3, что показывает, что алгоритм Кадана действительно имеет перекрывающиеся подзадачи.

Алгоритм Кадана обычно реализуется с использованием подхода DP снизу вверх, чтобы воспользоваться преимуществами перекрывающихся подзадач и вычислить каждую подзадачу только один раз, следовательно, превратив ее в O (n).