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.
(2nd Question form Amazon 1st telephonic)

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;

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.