Maximum sum such that no two elements are adjacent

Problem

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

Solution

Simplest solution is to sum all the elements in the array, which are not adjacent and find out max sum. But this solution is not efficient. 

We can device this problem in smaller problem, like if we find out for a sub set of array the max sum once we can re-use this sum. 

Solution below implements both the approaches, one with all permutations and second using dynamic programing.

  
public class MaxSumWithoutAdjecent {
    private int[] dp;

    public MaxSumWithoutAdjecent(int size){
        setInputSize(size);
    }

    public void setInputSize(int size){
        dp = new int[size +1];
        for (int i=0; i < dp.length; i++)
            dp[i] = -1;
    }

    public int maxSumByDp(int[] array, int index){
        if (index >= array.length)
            return 0;
        if (dp[index] != -1)
            return dp[index];

        int max = Math.max( array[index] + maxSum(array, index + 2), maxSum(array, index + 1));
        dp[index] = max;
        return max;
    }

    public static void main(String[] args) {
        int[] array = {5,  5, 10, 40, 50, 35};

        MaxSumWithoutAdjecent maxsummer = new MaxSumWithoutAdjecent(array.length);

        System.out.println(maxSum(array, 0));
        System.out.println(maxsummer.maxSumByDp(array, 0));

        int[] array1 = {3, 2, 5, 10, 7};
        maxsummer.setInputSize(array1.length);
        System.out.println(maxSum(array1, 0));
        System.out.println(maxsummer.maxSumByDp(array1, 0));
    }

    public static int maxSum(int[] array, int index){
        if (index >= array.length)
            return 0;
        return Math.max( array[index] + maxSum(array, index + 2), maxSum(array, index + 1));
    }
}

Comments are welcome. Question source geeksforgeeks