Maximum sum of non consecutive elements

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

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.

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.

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

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

The solution by @Ismail Badawi does not seem to work in the following case: Let us take the array: 8, 3, 1, 7 Then in this case, the algo returns max sum = 9 whereas it should be 15.

A solution to correct it is given an array A[0..n], let M(i) be the optimal solution using the elements with indices 0..i. Then M(0) = A[0], and M(i) = max(M(i - 1), M(i - 2) + A[i], M(i-3) + A[i]) for i = 3, ..., n. M(n) is the solution we want. This is O(n).

IIUC: say your array is 1,2,3,4,5 then 3+5 would be 'correct' and 4+5 not, this means you'll have to find the largest numbers and check if they are consecutive. So an algorithm would be to make use of a second array, for the number of elements you need to add which you fill by traversing the original array and finding the largest non-consecutive integers, then add this up.

For the above array I guess [1,3], [1,4], [1,5], [1,3,5], [2,4], [2,5], [3,5] would be valid non-consecutive integers to be summed, the max sum would be 9 in this case [1,3,5]. So, to adapt the above algorithm, I would suggest you step through the array using several temporary arrays to find all the non-consecutive integer lists, and then check which is the largest. Keep in mind that 'most elements' does not mean 'largest sum'.

Dynamic programming solution is the most elegant of all. And it serves for any value of the distance between two numbers that should not be considered. But for k= 1, which is for consecutive numbers constraint, I tried using backtracking.

There are different patterns to be compared for the maximum sum. Below is the list :

Number of patterns for 1 = 1    
[1]
Number of patterns for 2 = 2    
[1][2]
Number of patterns for 3 = 2
[1, 3][2]
Number of patterns for 4 = 3
[1, 3][1, 4][2, 4]
Number of patterns for 5 = 4
[1, 3, 5][1, 4][2, 4][2, 5]
Number of patterns for 6 = 5
[1, 3, 5][1, 3, 6][1, 4, 6][2, 4, 6][2, 5]
Number of patterns for 7 = 7
[1, 3, 5, 7][1, 3, 6][1, 4, 6][1, 4, 7][2, 4, 6][2, 4, 7][2, 5, 7]
Number of patterns for 8 = 9
[1, 3, 5, 7][1, 3, 5, 8][1, 3, 6, 8][1, 4, 6, 8][1, 4, 7][2, 4, 6, 8][2, 4, 7][2, 5, 7][2, 5, 8]
Number of patterns for 9 = 12
[1, 3, 5, 7, 9][1, 3, 5, 8][1, 3, 6, 8][1, 3, 6, 9][1, 4, 6, 8][1, 4, 6, 9][1, 4, 7, 9][2, 4, 6, 8][2, 4, 6, 9][2, 4, 7, 9][2, 5, 7, 9][2, 5, 8] 

Following is the code in java:

public class MaxSeqRecursive {

    private static int num = 5;
    private static int[] inputArry = new int[] { 1,3,9,20,7 };
    private static Object[] outArry;
    private static int maxSum = 0;

    public static void main(String[] args) {

        List<Integer> output = new ArrayList<Integer>();
        output.add(1);
        convert(output, -1);
        for (int i = 0; i < outArry.length; i++) {
            System.out.print(outArry[i] + ":");
        }

        System.out.print(maxSum);
    }

    public static void convert( List<Integer> posArry, int prevValue) {

        int currentValue = -1;

        if (posArry.size() == 0) {
            if (prevValue == 2) {
                return;
            } else {
                posArry.add(2);
                prevValue = -1;
            }

        }

        currentValue = (int) posArry.get(posArry.size() - 1);

        if (currentValue == num || currentValue == num - 1) {
            updateMax(posArry);
            prevValue = (int) posArry.get(posArry.size() - 1);
            posArry.remove(posArry.size() - 1);
        } else {
            int returnIndx = getNext(posArry, prevValue);
            if (returnIndx == -2)
                return;

            if (returnIndx == -1) {
                prevValue = (int) posArry.get(posArry.size() - 1);
                posArry.remove(posArry.size() - 1);
            } else {
                posArry.add(returnIndx);
                prevValue = -1;
            }
        }
        convert(posArry, prevValue);
    }

    public static int getNext( List<Integer> posArry, int prevValue) {
        int currIndx = posArry.size();
        int returnVal = -1;
        int value = (int) posArry.get(currIndx - 1);

        if (prevValue < num) {
            if (prevValue == -1)
                returnVal = value + 2;
            else if (prevValue - value < 3)
                returnVal = prevValue + 1;
            else
                returnVal = -1;
        }

        if (returnVal > num)
            returnVal = -1;

        return returnVal;
    }

    public static void updateMax(List posArry) {
        int sum = 0;
        for (int i = 0; i < posArry.size(); i++) {
            sum = sum + inputArry[(Integer) posArry.get(i) - 1];
        }
        if (sum > maxSum) {
            maxSum = sum;
            outArry = posArry.toArray();
        }
    }
}

Time complexity: O( number of patterns to be compared) 

Another Java Implementation ( runs in linear time )

public class MaxSum {

private static int ofNonConsecutiveElements (int... elements) {
    int maxsofar,maxi2,maxi1;

    maxi1 = maxsofar = elements[0];
    maxi2 = 0;

    for (int i = 1; i < elements.length; i++) {
        maxsofar =  Math.max(maxi2 + elements[i], maxi1);
        maxi2 =  maxi1;
        maxi1 = maxsofar;
    }
    return maxsofar;        
}

public static void main(String[] args) {
    System.out.println(ofNonConsecutiveElements(6, 4, 2, 8, 1));
}
}

My solution is O(N) time and O(1) space.

private int largestSumNonConsecutive(int[] a) {
    return largestSumNonConsecutive(a, a.length-1)[1];
}
private int[] largestSumNonConsecutive(int[] a, int end) {  //returns array largest(end-1),largest(end)
    if (end==0) return new int[]{0,a[0]};

    int[] largest = largestSumNonConsecutive(a, end-1);
    int tmp = largest[1];
    largest[1] = Math.max(largest[0] + a[end], largest[1]);
    largest[0] = tmp;

    return largest;
}

int nonContigousSum(vector<int> a, int n) {
    if (n < 0) {
        return 0;
    }
    return std::max(nonContigousSum(a, n - 1), nonContigousSum(a, n - 2) + a[n]);
}

this is the recursive approach with the help of which we can solve this question (OPTIMAL SUB-STRUCTURE HALLMARK OF DYNAMIC PROGRAMMING. Here we are considering two cases, in first we exclude a[n] and in the second we include a[n] and return the max of those sub cases found. We are basically finding all the subsets of the array and returning the length of the non-contiguous array with max sum. Use tabulation or memoization for avoiding same sub-problems.

A penny from me.

public class Problem {

  /**
   * Solving by recursion, top down approach. Always try this recursion approach and then go with
   * iteration. We have to add dp table to optimize the time complexity.
   */
  public static int maxSumRecur(int arr[], int i) {
    if(i < 0) return 0;
    if(i == 0) return arr[0];
    if(i == 1) return Math.max(arr[0], arr[1]);

    int includeIthElement = arr[i] + maxSumRecur(arr, i-2);
    int excludeIthElement = maxSumRecur(arr, i-1);
    return Math.max(includeIthElement, excludeIthElement);
  }

  /**
   * Solving by iteration. Bottom up approach.
   */
  public static void maxSumIter(int arr[]) {
    System.out.println(Arrays.toString(arr));
    int dp[] = new int[arr.length];
    dp[0] = arr[0];
    dp[1] = Math.max(arr[0], arr[1]);

    for(int i=2; i <= arr.length - 1; i++) {
      dp[i] = Math.max(arr[i] + dp[i-2], dp[i-1]);
    }

    System.out.println("Max subsequence sum by Iteration " + dp[arr.length - 1] + "\n");
  }

  public static void maxSumRecurUtil(int arr[]) {
    System.out.println(Arrays.toString(arr));
    System.out.println("Max subsequence sum by Recursion " + maxSumRecur(arr, arr.length - 1) +
        "\n");
  }

  public static void main(String[] args) {
    maxSumRecurUtil(new int[]{5, 5, 10, 100, 10, 5});
    maxSumRecurUtil(new int[]{20, 1, 2, 3});

    maxSumIter(new int[]{5, 5, 10, 100, 10, 5});
    maxSumIter(new int[]{20, 1, 2, 3});

  }

}

Make a list of numbers that is the odd or even sums corresponding to each number so far; e.g. for input of [1,2,4,1,2,3,5,3,1,2,3,4,5,2] the odd-even sums would be [1,2,5,3,7,6,12,9,13,11,16,15,21,17]

Now walk the list backwards greedily summing but skipping those elements whose odd/even sum is less than that of next-to-be-considered element.

src = [1,2,4,1,2,3,5,3,1,2,3,4,5,2]

odd_even_sums = src[:2]
for i in xrange(2,len(src)):
    odd_even_sums.append(src[i] + odd_even_sums[i-2])

best = []
for i in xrange(len(src)-1,-1,-1):
    if i == 0:
        best.append(i)
    elif odd_even_sums[i-1] > odd_even_sums[i]:
        pass
    elif odd_even_sums[i-1] == odd_even_sums[i]:
        raise Exception("an exercise for the reader")
    else:
        best.append(i)

best.reverse()

print "Best:",",".join("%s=%s"%(b,src[b]) for b in best)
print "Scores:",sum(odd_even_sums[b] for b in best)

Outputs:

Best: 0=1,1=2,2=4,4=2,6=5,8=1,10=3,12=5
Scores: 77

public static int findMaxSum(int[] a){
        int sum0=0; //will hold the sum till i-2        
        int sum1=0;//will hold the sum till i-1
        for(int k : a){
            int x=Math.max(sum0+k, sum1);//max(sum till (i-2)+a[i], sum till (i-1))
            sum0=sum1;
            sum1=x;
        }
        return sum1;
    }

Below is the crux of algorithm:

max(max sum till (i-2)+a[i], max sum till (i-1))

O(N) time complexity and O(1) space complexity.

A rather naive yet complete implementation. Recursion equation is T(n) = n^2 + nT(n-3), which if I'm not wrong leads to exponential time. The (n-3) comes from the fact a number cannot add with itself/previous/next numbers.

The program reports the constituent list that makes up the sum (there are multiple, exponentially growing, of these lists, but it just picks one).

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class MaxSumNoAdjacent {

    private static class Sum {
        int sum;
        List<Integer> constituents = new ArrayList<>();

        Sum(int sum, List<Integer> constituents) {
            this.sum = sum;
            this.constituents = constituents;
        }

        @Override
        public String toString() {
            return "sum: " + sum + " " + constituents.toString(); 
        }
    }

    public static Sum maxSum(int[] arr) {
        List<Integer> input = new ArrayList<>();
        for (int i : arr) {
            if (i != Integer.MIN_VALUE) { //Integer.MIN_VALUE indicates unreachability
                input.add(i);
            }
        }

        if (input.size() == 0) {
            return null;
        }

        if (input.size() == 1) {
            List<Integer> constituents = new ArrayList<>();
            constituents.add(input.get(0));
            return new Sum(input.get(0), constituents);
        }

        if (input.size() == 2) {
            int max = Math.max(input.get(0), input.get(1));
            List<Integer> constituents = new ArrayList<>();
            constituents.add(max);
            return new Sum(max, constituents);
        }

        Map<Integer, int[]> numberAndItsReachability = new HashMap<>();
        for (int i = 0; i < input.size(); i++) {
            int[] neighbours = new int[input.size()];
            if (i > 0) {
                neighbours[i-1] = Integer.MIN_VALUE; //unreachable to previous
            }

            if (i < input.size()-1) {
                neighbours[i+1] = Integer.MIN_VALUE; //unreachable to next
            }

            neighbours[i] = Integer.MIN_VALUE; //unreachable to itself

            for (int j = 0; j < neighbours.length; j++) {
                if (neighbours[j] == 0) {
                    neighbours[j] = input.get(j); //remember values of reachable neighbours
                }
            }

            numberAndItsReachability.put(input.get(i), neighbours);
        }

        Sum maxSum = new Sum(Integer.MIN_VALUE, null);
        for (Entry<Integer, int[]> pair : numberAndItsReachability.entrySet()) {
            Sum sumMinusThisNumber = maxSum(pair.getValue()); //call recursively on its reachable neighbours
            if (sumMinusThisNumber != null) {
                int candidateSum = sumMinusThisNumber.sum + pair.getKey();
                if (maxSum.sum < candidateSum) {
                    sumMinusThisNumber.constituents.add(pair.getKey());
                    maxSum = new Sum(candidateSum, sumMinusThisNumber.constituents);
                }
            }

        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr1 = {3,2,5,10,7};
        int[] arr2 = {3,2,7,10};
        int[] arr3 = {5,5,10,40,50,35};
        int[] arr4 = {4,4,4,4};
        System.out.println(maxSum(arr1).toString());
        System.out.println(maxSum(arr2).toString());
        System.out.println(maxSum(arr3).toString());
        System.out.println(maxSum(arr4).toString());
    }

}

Here is a C# version for reference (you may refer to: http://dream-e-r.blogspot.com/2014/07/maximum-sum-of-non-adjacent-subsequence.html):

In-order to solve a problem using dynamic programming there should be a solution which has optimal substructure and overlapping sub problems properties. And the current problem has optimal substructure property. Say, f(i) is defined as maximum subsequence sum of non adjacent elements for 'i' items, then

f( i) = 0 if i = 0 max (f(i-1), f(i-2) + a[i])

Below is the algorithm for the same (no te it can solved without the encapsulating data in 'record' - i just preferred it this way) - which should illustrate the above idea:

int FindMaxNonAdjuscentSubsequentSum(int[] a)
        {
            a.ThrowIfNull("a");
            if(a.Length == 0)
            {
                return 0;
            }
            Record r = new Record()
            {
                max_including_item = a[0],
                max_excluding_item = 0
            };
            for (int i = 1; i < a.Length; i++)
            {
                var t = new Record();
                //there will be only two cases
                //1. if it includes the current item, max is maximum of non adjuscent sub
                //sequence sum so far, excluding the last item
                t.max_including_item = r.max_excluding_item + a[i];
                //2. if it excludes current item, max is maximum of non adjuscent subsequence sum
                t.max_excluding_item = r.Max;
                r = t;
            }
            return r.Max;
        }

Unit Tests

[TestMethod]
        [TestCategory(Constants.DynamicProgramming)]
        public void MaxNonAdjascentSubsequenceSum()
        {
            int[] a = new int[] { 3, 2, 5, 10, 7};
            Assert.IsTrue(15 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 3, 2, 5, 10 };
            Assert.IsTrue(13 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 5, 10, 40, 50, 35 };
            Assert.IsTrue(80 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 1, -1, 6, -4, 2, 2 };
            Assert.IsTrue(9 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 1, 6, 10, 14, -5, -1, 2, -1, 3 };
            Assert.IsTrue(25 == this.FindMaxNonAdjuscentSubsequentSum(a));
        }

where

public static int Max(int a, int b)
        {
            return (a > b) ? a : b;
        }
        class Record
        {
            public int max_including_item = int.MinValue;
            public int max_excluding_item = int.MinValue;
            public int Max
            {
                get
                {
                    return Max(max_including_item, max_excluding_item);
                }
            }
        }

public static int maxSumNoAdj(int[] nums){
    int[] dp = new int[nums.length];
    dp[0] = Math.max(0, nums[0]); // for dp[0], select the greater value (0,num[0])
    dp[1] = Math.max(nums[1], Math.max(0, dp[0]));    
    int maxSum = Math.max(dp[0], dp[1]);
    for(int i = 2; i < nums.length; i++){
        int ifSelectCurrent = Math.max(nums[i] + dp[i-2], dp[i-2]);// if select, there are two possible
        int ifNotSelectCurrent = Math.max(dp[i-1], dp[i-2]);        // if not select, there are two posible
        dp[i] = Math.max(ifSelectCurrent, ifNotSelectCurrent);      // choose the greater one
        maxSum = Math.max(dp[i], maxSum);   // update the result
    }
    return maxSum;
}

public static void main(String[] args) {
    int[] nums = {-9, 2, 3, -7, 1, 1};
    System.out.println(maxSumNoAdj(nums));
}