Piyush sorry dude but this will not work say original array be 6 8 4 1 2 3 then ur new array be 6 8 10 10 12 13 //but original answer is 12
On Tue, Jul 19, 2011 at 3:49 PM, Piyush Sinha <[email protected]>wrote: > 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. > -- **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.
