This is a simple dp problem .
define for each i following 2 quantities :
best1[i] : best sum in similar constraint of first i elements only when last
( ith ) term is always included
best2[i] : best sum in similar constraint of the first i elements only when
last (ith ) term is NOT included
so we can define best1 and best2 in terms of smaller bests like this :
best1[i] : max{ (best2[i-1]+a[i]) , a[i] }
best2[i]: max{ (best1[i-1] + a[i] ) , (best2[i-1]+a[i] ) , a[i] }
best1[0]=a[0] ans best2[0]=0;
finally we are concerned in :
max { best1[last] , best2[last] }
so we can find the answer in O(n)
On Fri, Oct 9, 2009 at 9:26 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)
>
> >
>
--
nikhil-
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
