I hope it can be solved using DP...check my algo below and give any counter
case if you get it...
1. Make an array S equal to the length of the given array where
S[0] = a[0] and S[1] = max(a[0],a[1])
2. for i:2 to n-1
S[i] = max(S[i-2]+a[i], S[i-1])
3. return S[n-1]
Hope the above algo works...
On Tue, Jul 19, 2011 at 2:59 PM, sagar pareek <[email protected]> wrote:
> Given an array all of whose elements are positive numbesr, find the maximum
> sum of a subsequence with the constraint that no 2 numbers in the sequence
> should be adjecent in the array.
>
> eg:-
> 3 2 7 10 should return (sum of 3 and 10)
> 3 2 5 10 7 should returnn 15 (sum of 3,5,7)
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
> --
> 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.
>
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* <https://www.facebook.com/profile.php?id=100000655377926> "NEVER SAY
NEVER"
*
--
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.
