An array on n integers is given. Find out the maximum sum of the elements of array such that no 2 elements are consecutive.
eg.
A[] = {1,2,3,4} Ans= 6
A[] = {1,-2,3,4} Ans=5
SOLUTION
int fun(int *array, int n){
int a=array[0], b=array[1], c=max(max(array[0]+array[2], array[2]), array[0]);
for ( int i=3; n-i;i++){
int temp=max(max( array[i], array[i] +b), array[i]+a);
a = b;
b = c;
c = temp;
}
return max(b,c);
}
Subscribe to:
Post Comments (Atom)
13 comments:
i think by applying DP we can solve it.
taking an array with dp[0]=a[0], dp[1]=a[1], dp[2] = max(a[2], a[0]+a[2]). by moving forward in the same way we can find out the max sum in O(n).
@placement2010:
Your idea is perfect, but require O(n) space. Solution I provided is O(1) space solution.
well it can be done without dp also
1. find the maximum no. in the array.
2.find another no. which is highest from the remaining elements and also not the consecutive left or right of the no. find in first step.
@above
ur algo is wrong, consider this case:
2 9 8 -2 1
well for this case it is correct
it gives 9 + 1=10
ya but for case like 5 9 8 2 1
it will not give correct output
thnx :)
but i think it can be fixed very easily
1. find the maximum no. in the array.Also store its left and right neighbor if they exist.Let these be max1, left and right respectively.
2.find another no. which is highest from the remaining elements and also not the consecutive left or right of the no. find in first step.Let tis number be num.
3.return max((max1+num),(left+right))
for example in 5 9 8 2 1
max1=9, left =5, right=8
num=2
max(9+2,8+5)=13
correct me if wrong
for ur case it works
9 + 1 = 10
it won't work for case like 5 9 8 2 1
forget the previous comment
@ above:
Two points:
1.In my case ans would be 11 ( 2+8+1).
2.Your max((max1+num),(left+right)) approach is wrong. I didn't ask for maximum sum of 2 elements, i asked for maximum sum rather.
ahh, misinterpret the question somehow :(
its ok.
more doubts = much clearer concepts :-)
yeah :)
Post a Comment