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.
sum = sum1 = array[0];
for(i=1; i<len; i++)
{
sum = MAX(sum2 + array[i], sum1);
sum2 = sum1;
sum1 = sum;
}
Read full article from Max possible sum of non-consecutive elements | PROGRAMMING INTERVIEWS
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);
sum2 = 0;S(-1) = 0;
if i=0, S(i) = T(0);
sum = sum1 = array[0];
for(i=1; i<len; i++)
{
sum = MAX(sum2 + array[i], sum1);
sum2 = sum1;
sum1 = sum;
}
Read full article from Max possible sum of non-consecutive elements | PROGRAMMING INTERVIEWS
