Алгоритм Кадане жадный или оптимизированный DP?
Я чувствую, что алгоритм Кадане - это модифицированная версия истинного динамического программного решения задачи о максимальных подрешетках. Почему я так чувствую? Я чувствую, потому что способ вычисления максимального подмассива может быть принят:
for(i=0;i<N;i++)
{
DP[i][A[i]]=true;
for(j= -ve maximum ;j<= +ve maximum ;j++)
if(DP[i-1][j])
DP[i][j+A[i]]=true;
}
Рецидив заключается в том, что если возможно сформировать j с подмассивом, заканчивающимся на i-1 элементах, то я могу сформировать j+A[i], используя i-й элемент, а также сформировать только A [i], запустив подмассив в i-й позиции А наконец, мы можем найти в этом массиве DP максимум j, помеченный как true!
Замечания: DP[i][j] представляет, если возможно сделать j, используя подмассив, заканчивающийся на i! Здесь я предполагаю, что j тоже может быть отрицательным. Теперь можно легко получить эту сумму + отрицательное число <сумма. Это означает, что добавление любых отрицательных индексов не поможет получить лучшую сумму, поэтому мы можем их отбросить! Более того, мы заботимся о максимальном J до i-1 и соединить его с i th элемент, который заставляет меня чувствовать, что это своего рода жадный выбор (просто потому, что максимум + элемент дает мне максимум).
ПРИМЕЧАНИЕ: я не изучал алгоритмы Greedy до сих пор, но у меня есть идея, что такое жадный выбор!
РЕДАКТИРОВАТЬ: SOmeone сказал, что мой алгоритм не имеет никакого смысла, поэтому я пытаюсь опубликовать свой код, чтобы прояснить себя. Я не воспринял это, поскольку они не плодотворны. Я повторяю, мое состояние определено так, как это возможно, чтобы сделать j, используя подмассив, заканчивающийся на i.
#include<bits/stdc++.h>
using namespace std;
int DP[101][101];
int main()
{
int i,j,ans=INT_MIN;
int A[]={3,-1,2,-1,5,-3};
int N=sizeof(A)/sizeof(int);
for(i=1;i<=N;i++)
{
if(A[i-1]>=0)
DP[i][A[i-1]]++;
for(j=0;j<=100;j++)
{
if(DP[i-1][j])
{
if(j+A[i-1]>=0)
DP[i][j+A[i-1]]++;
}
if(DP[i][j])
ans=max(ans,j);
}
}
cout<<ans<<"\n";
return 0;
}
Выход 8
5 ответов
Kadane's - это итеративный алгоритм динамического программирования.
Очень часто оптимизируют итерационные алгоритмы DP для удаления одного измерения матрицы DP вдоль главной оси прогрессии алгоритма.
Например, обычный алгоритм "самой длинной общей подпоследовательности" обычно описывается двумерной матрицей, но если алгоритм выполняется слева направо, то вам действительно нужно место только для двух столбцов.
Алгоритм Кадане - это аналогичная оптимизация, применяемая к одномерной задаче, поэтому весь массив DP исчезает. Код DP в вашем вопросе по какой-то причине имеет 2D-матрицу. Не знаю почему - в этом нет смысла.
Этот сайт довольно хорошо объясняет происхождение: https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6
Я думаю, что это жадный алгоритм, потому что алгоритм Каданеса находит максимальную сумму на каждом шаге, а затем находит общее решение.
Алгоритм Кадане можно рассматривать и как жадный, и как DP. Как мы видим, мы сохраняем текущую сумму целых чисел, и когда она становится меньше 0, мы сбрасываем ее до 0 (жадная часть). Это связано с тем, что продолжение с отрицательной суммой намного хуже, чем перезапуск с новым диапазоном. Теперь его также можно рассматривать как DP, на каждом этапе у нас есть 2 варианта: либо взять текущий элемент и продолжить с предыдущей суммой, либо перезапустить новый диапазон. Оба варианта учитываются при реализации.
Жадный Сол
# Python program to find maximum contiguous subarray
# Function to find the maximum contiguous subarray
from sys import maxint
def maxSubArraySum(a,size):
max_so_far = -maxint - 1
max_ending_here = 0
for i in range(0, size):
max_ending_here = max_ending_here + a[i]
if (max_so_far < max_ending_here):
max_so_far = max_ending_here
if max_ending_here < 0:
max_ending_here = 0
return max_so_far
# Driver function to check the above function
a = [-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7]
print "Maximum contiguous sum is", maxSubArraySum(a,len(a))
ДП Сол
# Python program to print largest contiguous array sum
from sys import maxsize
# Function to find the maximum contiguous subarray
# and print its starting and end index
def maxSubArraySum(a,size):
max_so_far = -maxsize - 1
max_ending_here = 0
start = 0
end = 0
s = 0
for i in range(0,size):
max_ending_here += a[i]
if max_so_far < max_ending_here:
max_so_far = max_ending_here
start = s
end = i
if max_ending_here < 0:
max_ending_here = 0
s = i+1
print ("Maximum contiguous sum is %d"%(max_so_far))
print ("Starting Index %d"%(start))
print ("Ending Index %d"%(end))
# Driver program to test maxSubArraySum
a = [-2, -3, 4, -1, -2, 1, 5, -3]
maxSubArraySum(a,len(a))
Как определено во введении в алгоритмы, «жадный алгоритм всегда делает выбор, который выглядит лучше всего в данный момент. То есть он делает локально оптимальный выбор в надежде, что этот выбор приведет к глобально оптимальному решению».
Алгоритм Кадане действительно ищет локально оптимальное решение с помощью
current_sum = max(0, current_sum + x); в то же время это также можно рассматривать как оптимизированное для пространства решение для динамического программирования -
dp[i] полагается только на
dp[i-1] следовательно, мы используем целочисленную переменную для экономии места.
Поэтому мне кажется, что функция перехода DP имеет жадный характер, что делает его похожим на DP и на жадность.
Я думаю, что трудно сказать, что это за алгоритм.
Но большая часть книги классифицирует этот алгоритм в разделе DP, потому что вы комбинируете решение из dp[n-1], чтобы найти решение для dp[n].
Примечание: я не понимаю, почему вы используете эту версию алгоритма, который O(n^2)Вы можете упростить этот алгоритм до O(n)
curmax=0
sol=0
for x in array
curmax+=a[x]
if(curmax<0)curmax=0
if(curmax>sol)sol=curmax