Maximum sum of non-adjacent numbers: algorithm explained.

I saw this algorithm at GeeksforGeeks.com. This is a really cool algorithm, but how it works is not really straightforward. This is my attempt at dissecting and explaining this algorithm. I would be explaining it step by step, bringing in restrictions and conditions step by step and improving the algorithm at each step to finally reach at the actual algorithm. The code from the website is pasted below for reference.

/*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; 
}

Note: All the numbers are non-negative numbers.

How do we solve this problem ? The first thing that comes to my mind is to pick the maximum number of non-adjacent elements from the list. More the elements, more the sum, right ? This would mean that we shall pick the elements on the odd or the even indices of the list.

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);
}

Let us modify the above code getting rid of the check for the odd/even index. Let’s have two variables for two sums, that don’t differentiate between odd or even chains. They store the local sums alternating between the odd chain and the even chain as we iterate though the list.

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);
}

But this algorithm has a flaw and does not give the maximum sum. Why ? Because we are restricting our sums to include elements from two chains(odd/even chains). There can be some big numbers on each of the chain which are non-adjacent but are not included our calculated sum.

This leads to a realization that we shall not skip any local maxima even though we might not maximize the number of elements we consider. Hence, the assumption that maximizing the number of elements maximizes the sum is an incorrect one. So, the algorithm should, in general, consider the maximum of odd and even chains at every point while iterating the list; this would mean that our final sum might be coming from the stitching of locally maximum odd and even chains.

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);
}

For the case where the list also includes negative-numbers, the current algorithm has two flaws and have to be addressed:

1. The initialization of prev_prev_sum to zero: For a list of just one negative number, and for the list of all negative numbers, the number zero would become the maximum sum which is not even in the list. For example: {-5}, {-10, -22, -18, -3, -100} — result = 0.
2. The summation: Assuming the first flaw is fixed by initializing the two previous sums to the first two elements of the list, for the list of all negative numbers, any addition of negative number results in a lesser sum than the original number. This would result in the first/second element of the list to wrongly be the result. For example: {-7, -10, -12, -2, -16} — result = -7; {-10, -5, -12, -1, -7} — result = -5. The actual result in these cases is the greatest number in the list i.e., -2 and -1 respectively.

The next level of difficulty would be to trace the elements that add up to the maximum sum, a topic for some other day.