Monday, January 2, 2012

Max possible sum of non-consecutive elements

Question: 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.

Answer: To solve these type of question, first thing is to find a recurring relation. In this case our recurring relation will tell the max sum till a given length. It means that we will get the max sum for running length of the array. If we denote the ith element as T(i) and max sum till ith element of the array as S(i), then

S(i) = MAX {S(i-1), S(i-2) + T(i) }

S(-1) = 0;
if i=0, S(i) = T(0);

Note: while developing this relationship, I assume array index is starting from 0.

Writing code for this problem is not a big deal now. Below is the code snippet for the same.
sum2 = 0;
sum = sum1 = array[0];

for(i=1; i<len; i++)
{
   sum = MAX(sum2 + array[i], sum1);
   sum2 = sum1;
   sum1 = sum;
}


2 comments:

  1. Below code works for -ve numbers :

    public static int findMaxSum(int arr[]) {
    if (arr.length == 0) return 0;
    if (arr.length == 1) return arr[0];
    int a = arr[0];
    int b = Math.max(arr[0], arr[1]);
    int c = b;

    for(int i=2; i<arr.length; i++) {
    c = Math.max(arr[i], Math.max(b, arr[i] + a));
    a = b; // a now becomes second last sum
    b = c; // b now becomes previous sum
    }

    return c;
    }

    Please correct me if i am wrong.

    ReplyDelete
  2. Nice answer - I ideone it, and it was correct - http://ideone.com/TYBCai.

    Thanks Vikram.

    ReplyDelete