Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
Может ли кто-нибудь помочь мне в понимании оптимальной субструктуры и проблемы перекрытия (хлеб и масло DP) я вышеупомянутое альго?
В соответствии с этим определением перекрывающихся подзадач рекурсивная формулировка алгоритма Кадане (f[i] = max(f[i - 1] + a[i], a[i])) не обладает этим свойством. Каждая подзадача будет вычисляться только один раз в наивной рекурсивной реализации.
Однако он показывает оптимальную субструктуру в соответствии с ее определением здесь: мы используем решение для небольших подзадач, чтобы найти решение наша задача (f[i] использует f[i - 1]).
Рассмотрим определение динамического программирования здесь:
В математике, информатике и экономике динамическое программирование - это метод решения сложных задач, разбивая их на более простые подзадачи. Он применим к проблемам, проявляющим свойства перекрывающихся подзадач 1 и оптимальной субструктуре (описанной ниже). Когда это применимо, метод занимает гораздо меньше времени, чем наивные методы, которые не используют перекрытие подзадачи (например, поиск по глубине).
Идея динамического программирования довольно проста. В общем, для решения данной проблемы нам необходимо решить разные части задачи (подзадачи), а затем объединить решения подзадач для достижения общего решения. Часто при использовании более наивного метода многие подзадачи генерируются и решаются много раз. Метод динамического программирования направлен на решение каждой подзадачи только один раз, что уменьшает количество вычислений
Это оставляет место для интерпретации того, можно ли считать алгоритм Кадана алгоритмом DP: он решает проблему, разбивая ее на более простые подзадачи, но его основной рекурсивный подход не создает перекрывающиеся подзадачи, что и является DP предназначен для эффективной работы - так что это поставит его вне специальности DP.
С другой стороны, вы могли бы сказать, что базовый рекурсивный подход не обязательно должен приводить к перекрывающимся подзадачам, но это сделало бы любой рекурсивный алгоритм алгоритмом DP, что дало бы DP слишком широкий охват на мой взгляд, Я не знаю ничего в литературе, который определенно решает это, однако, поэтому я не буду отмечать ученика или не рассказывать книгу или статью так, как они ее обозначали.
Поэтому я бы сказал, что это не алгоритм DP, а только жадный и/или рекурсивный, в зависимости от реализации. Я бы назвал его жадным с алгоритмической точки зрения по причинам, перечисленным выше, но объективно я бы рассмотрел другие интерпретации так же корректно.