Max Possible Sum Of Non-Consecutive Elements

There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum.


Example: If given array is (6, 4, 2, 8, 1), the answer will be 14 (8+6). This is the maximum sum we can obtain without taking two consecutive elements.


Java Code : 

public class MaxNonConsecutiveSum {
 public static void main(String[] args) {
  int[] a = { 6, 4, 2, 8, 1 };
  System.out.println(getMaxNonConsecutiveSum(a, 0));
  System.out.println(getMaxNonConsecutiveSumDp(a));
 }

 private static int getMaxNonConsecutiveSum(int[] a, int pos) {
  if (pos >= a.length)
   return 0;

  // If we include element at position 'i', we should not include position
  // 'i+1'.So we start from 'i+2'
  // if we don't select position 'i', then we start recurrence from i+1
  return max(a[pos] + getMaxNonConsecutiveSum(a, pos + 2),
    getMaxNonConsecutiveSum(a, pos + 1));
 }

 private static int max(int a, int b) {
  return a > b ? a : b;
 }

 private static int getMaxNonConsecutiveSumDp(int[] a) {
  if (a.length == 0)
   return 0;

  if (a.length == 1)
   return a[0];

  // create a temporary array to hold max non consecutive sums as sub
  // problems'
  int[] dp = new int[a.length];
  dp[0] = a[0];
  dp[1] = max(a[0], a[1]);
  for (int i = 2; i < a.length; i++) {
   dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
  }
  return dp[a.length - 1];
 }
}

Refer : http://tech-queries.blogspot.com/2009/05/max-possible-sum-of-non-consecutive.html
http://www.geeksforgeeks.org/archives/3133