Я видел этот алгоритм на GeeksforGeeks.com. Это действительно крутой алгоритм, но как он работает, на самом деле непросто. Это моя попытка проанализировать и объяснить этот алгоритм. Я буду объяснять это шаг за шагом, вводя ограничения и условия шаг за шагом и улучшая алгоритм на каждом шаге, чтобы наконец достичь фактического алгоритма. Код с веб-сайта вставлен ниже для справки.

/*Function to return max sum such that no two elements 
are adjacent */
int FindMaxSum(int arr[], int n) 
{ 
int incl = arr[0]; 
int excl = 0; 
int excl_new; 
int i;
for (i = 1; i < n; i++) 
{ 
 /* current max excluding i */
 excl_new = (incl > excl)? incl: excl;
/* current max including i */
 incl = excl + arr[i]; 
 excl = excl_new; 
}
/* return max of incl and excl */
return ((incl > excl)? incl : excl); 
}
/* Driver program to test above function */
int main() 
{ 
int arr[] = {5, 5, 10, 100, 10, 5}; 
int n = sizeof(arr) / sizeof(arr[0]); 
printf(“%d n”, FindMaxSum(arr, n)); 
return 0; 
}

Примечание. Все числа являются неотрицательными.

Как решить эту проблему? Первое, что приходит в голову, это выбрать из списка максимальное количество несмежных элементов. Больше элементов, больше сумма, верно? Это означало бы, что мы будем выбирать элементы по четным или нечетным индексам списка.

int maxSum(int list[], int list_len)
{
int sum_even = 0;
int sum_odd = 0;
int i;
for (i = 0 ; i < list_len; i++) {    
    if (i % 2 == 0)
        sum_even = sum_even + list[i];
    else
        sum_odd = sum_odd + list[i];
}

return (sum_even > sum_odd ? sum_even : sum_odd);
}

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

int maxSum(int list[], int list_len)
{
int prev_prev_sum = 0;
int prev_sum = 0;
int i, current_sum;

for (i = 0 ; i < list_len; i++) {    
    current_sum = prev_prev_sum + list[i];
    /* Sum calculated. Ready the variables for the next iteration */
    prev_prev_sum = prev_sum;
    prev_sum = current_sum;
}

return (prev_prev_sum > prev_sum ? prev_prev_sum : prev_sum);
}

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

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

int maxSum(int list[], int list_len)
{
int prev_prev_sum = 0;
int prev_sum = list[0];
int i, current_sum;
for (i = 1; i < list_len; i++) {
    current_sum = prev_prev_sum + list[i];
    /* Sum calculated. Ready the variables for the next iteration */
    prev_prev_sum = prev_prev_sum>prev_sum ? prev_prev_sum:prev_sum;
    prev_sum = current_sum;
}

return (prev_prev_sum > prev_sum ? prev_prev_sum: prev_sum);
}

В случае, когда список также включает отрицательные числа, текущий алгоритм имеет два недостатка, которые необходимо устранить:

  1. Инициализация prev_prev_sum нулевым значением: для списка только одного отрицательного числа и для списка всех отрицательных чисел нулевое число станет максимальной суммой, которой даже нет в списке. Например: {-5}, {-10, -22, -18, -3, -100} - результат = 0.
  2. Суммирование. Предполагая, что первый недостаток устранен путем инициализации двух предыдущих сумм для первых двух элементов списка, для списка всех отрицательных чисел любое добавление отрицательного числа дает меньшую сумму, чем исходный номер. Это приведет к тому, что первый / второй элемент списка будет ошибочным результатом. Например: {-7, -10, -12, -2, -16} - результат = -7; {-10, -5, -12, -1, -7} - результат = -5. Фактический результат в этих случаях - наибольшее число в списке, то есть -2 и -1 соответственно.

Следующим уровнем сложности будет отслеживание элементов, которые в сумме составляют максимальную сумму, тема для какого-нибудь другого дня.