On Oct 9, 8:56 am, ankur aggarwal <[email protected]> wrote:
> 2. 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.
>
> 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)
Quite Simple:
void FindMaxSum(int buf[], size_t cnt)
{
int incl = 0; // max sequence including the previous item
int excl = 0; // max sequence excluding the previous item
int excl_new=0;
for (size_t i = 0; i < cnt; i++)
{
// current max excluding i
if (incl > excl) excl_new = incl;
else
excl_new = excl;
// current max including i
incl = excl + buf[i];
excl = excl_new;
}
cout << "\nmax sum = " << ((incl > excl)? incl : excl) << endl;
}
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
