Maximum sum of non consecutive elements

/**
 * Given an array of positive numbers, find the maximum sum of elements such
 * that no two adjacent elements are picked
 * Top down dynamic programming approach without memorisation.
 * An alternate to the bottom up approach.
 */

public class MaxSumNonConsec {

public static int maxSum(int a[], int start, int end) {
    int maxSum = 0;

    // Trivial cases
    if (start == end) {
        return a[start];
    } else if (start > end) {
        return 0;
    } else if (end - start == 1) {
        return a[start] > a[end] ? a[start] : a[end];
    } else if (start < 0) {
        return 0;
    } else if (end >= a.length) {
        return 0;
    }

    // Subproblem solutions, DP
    for (int i = start; i <= end; i++) {
        int possibleMaxSub1 = maxSum(a, i + 2, end);
        int possibleMaxSub2 = maxSum(a, start, i - 2);

        int possibleMax = possibleMaxSub1 + possibleMaxSub2 + a[i];
        if (possibleMax > maxSum) {
            maxSum = possibleMax;
        }
    }

    return maxSum;
}

public static void main(String args[]) {
    int a[] = { 8, 6, 11, 10, 11, 10 };
    System.out.println(maxSum(a, 0, a.length - 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.

O(N) in time and O(1) in space (DP) solution:

int dp[2] = {a[0], a[1]};
for(int i = 2; i < a.size(); i++)
{
    int temp = dp[1];
    dp[1] = dp[0] + a[i];
    dp[0] = max(dp[0], temp);
}    
int answer = max(dp[0], dp[1]);

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.