int FindMaxSum(int array[],int i)
{
if(i>Size) //Size is array size, considered as global variable in
my solution
return 0;
int Sum1 = FindMaxSum(array,i+2);//cannot chose i+1 as that will
make it adjacent
int Sum2 = FindMaxSum(array,i+3);//at any place I cannot chose i
+1, so I chose i+2 above
//But chosing i+2 will mean cannot chose i+3 and I will miss that
route. So again call
//FindMaxSum with i+3;
if(Sum1>Sum2) return Sum1+array[i];
else return Sum2+array[i];
}
This FindMaxSum must be called by some function like
F()
{
int Sum1 = FindMaxSum(array,0);//0 = first element of array
int Sum2 = FindMaxSum(array,1);
//Larger of Sum1 and Sum2 will be the answer.
}
This is a brute force approach and many calculations are done
repetedly. Dynamic Programing will improve the performance.
On Jun 11, 8:41 pm, divya <[email protected]> wrote:
> Given an array all of whose elements are positive numbers, find the
> maximum sum of a subsequence with the constraint that no 2 numbers in
> the sequence should be adjacent in the array.
>
> Eg.
>
> i) 3 2 7 10 should return 13 (sum of 3 and 10)
>
> ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
