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)
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);
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.
How about 20? 6+4+2+8. 2 and 0 are not consecutive.
Consecutive means at consecutive position in input array.
hi AAkash how your mind strike with this approach plz through some light on recuaance relation
@Anonymous: This is a Dynamic Programming approach. Since we are not allowed to pick adjacent elements only options for S(i) are either:
1) S(i-1) (which may or may not include T(i-1) ). Since we are not including T(i) so while calculating S(i+1), T(i) will surely be missing. This will ensure that no adjacent element are together.
2) T(i) + S(i-2), this will insure that we are not including T(i-1), so if S(i-2) has T(i-2), again no adjacent element will be together.
Now we want maximum result so S(i) = MAX {S(i-1), S(i-2) + T(i) }
Example:
(6, 4, 2, 8, 1)
S(0) = 0
S(1) = 6
s(2) = Max(6, 4+0) = 6
s(3) = Max (S(2), 2 + S(1)) = Max(6, 8) = 8
s(4) = Max (S(3), 8 + S(2)) = Max(8, 8+6) = 14
s(5) = Max (S(4), 1 + S(3)) = Max(14, 1 + 8) = 14
What if you are allowed to select a certain number of integers from anywhere in the list that don't have to follow the consecutive rule? For example, from your list of { 6, 4, 2, 8, 1}, say you can take one additional integer from anywhere. Would that still be a dynamic programming solution?
@Chris: Can you please elaborate? I couldn't get your point.
The problem can be generalized as finding the maximum sum such that every element in the sum is at-least k distance apart.
for a general value of k
The recurrence becomes :
S(i)= max{S(i-k),T(i)+S(i-2k)}
S(0)=T(0)
@Mayank: Yes, we can generalize it but I think there should be a correction. It should be
S(i)= max{S(i-k),T(i)+S(i-k-1)}
Shouldn't it be :
S(i)= max{S(i-1),T(i)+S(i-k-1)}
??
@Anonymous: Yes, it should be like that. Thanks for the correction!
I copy-paste it from Mayank's comment and made changes. Somehow I missed that change but that was in mind.
i have used a simple logic comparatively, this is generating correct o/p for all i/p sets i have tried...but i am not sure that it will pass all the test cases.
will this generate correct o/p every time?
int sum=0;
for(int i=0;iarray[i+1])
{
sum=sum+array[i];
i+=2;
}
else
{
sum=sum+array[i+1];
i+=3;
}
}
cout<<"\nMaximum sum is : "<<sum;
@Varun: Looks like your code is not complete so no one can comment on it.
In the code you posted, we are seeing an 'else' part without a corresponding 'if'.