Maximum sum of non consecutive elements

Question

Given an array of positive integers, what's the most efficient algorithm to find non-consecutive elements from this array which, when added together, produce the maximum sum?

Answer 1

Dynamic programming? Given an array A[0..n], let M(i) be the optimal solution using the elements with indices 0..i. Then M(-1) = 0 (used in the recurrence), M(0) = A[0], and M(i) = max(M(i - 1), M(i - 2) + A[i]) for i = 1, ..., n. M(n) is the solution we want. This is O(n). You can use another array to store which choice is made for each subproblem, and so recover the actual elements chosen.

Answer 2

Let A be the given array and Sum be another array such that Sum[i] represents the maximum sum of non-consecutive elements from arr[0]..arr[i].

We have:

Sum[0] = arr[0] Sum[1] = max(Sum[0],arr[1]) Sum[2] = max(Sum[0]+arr[2],Sum[1]) ... Sum[i] = max(Sum[i-2]+arr[i],Sum[i-1]) when i>=2 

If size is the number of elements in arr then sum[size-1] will be the answer.

One can code a simple recursive method in top down order as:

int sum(int *arr,int i) {         if(i==0) {                 return arr[0];         }else if(i==1) {                 return max(arr[0],arr[1]);         }         return max(sum(arr,i-2)+arr[i],sum(arr,i-1)); } 

The above code is very inefficient as it makes exhaustive duplicate recursive calls. To avoid this we use memoization by using an auxiliary array called sum as:

int sum(int *arr,int size) {         int *sum = malloc(sizeof(int) * size);         int i;          for(i=0;i<size;i++) {                 if(i==0) {                         sum[0] = arr[0];                 }else if(i==1) {                         sum[1] = max(sum[0],arr[1]);                 }else{                         sum[i] = max(sum[i-2]+arr[i],sum[i-1]);                 }         }             return sum[size-1]; } 

Which is O(N) in both space and time.