Step 1 Find the max element position in the array. ( save position maxElement variable ). This takes O (n)
Step 2 Find the max element position again ( this time exclude maxElement, (maxElement+1) and (maxElement-1) in the comparision ) save this position to secondElementRequired variable This takes O ( n ) return array[ maxElement ] + array [secondElementRequired ] Thank you, Samba On Mon, Aug 1, 2011 at 5:31 AM, Abhishek Gupta <[email protected]>wrote: > Ya got it. > thanks a lot. > I was looking for dynamic solution only but unable to solve one. > > > On Mon, Aug 1, 2011 at 2:04 PM, Prakash D <[email protected]> wrote: > >> I just thought of an O(n) dp solution >> >> let a[]=5,2,1,7,9,11 >> >> traverse from i=0 to n-1 >> >> we define arr[i]= a[i]+max(arr[i-2],arr[i-3)); >> >> >> first arr[0]= 5 + max( a[-2], a[-3]) = 5 >> >> arr[1]= 2 >> >> arr[2]=1 + 5 >> >> arr[3]= 7 + max(5,2) = 7+ 5 = 12 >> >> then arr[4]= 9 + max(2,6) = 15 >> >> then arr[5]= 11 + max(6,12) = 11+12 = 23 >> >> >> now soln= max( arr[n-1], arr[n-2]) = 23 >> >> >> hope i'm correct .. >> >> >> regards, >> >> D.Prakash, >> IT, IIIrd year, CEG. >> >> >> >> >> >> >> On Mon, Aug 1, 2011 at 1:39 PM, Abhishek Gupta <[email protected]>wrote: >> >>> @Prakash >>> can you post your solution please >>> >>> >>> On Mon, Aug 1, 2011 at 1:39 PM, Abhishek Gupta >>> <[email protected]>wrote: >>> >>>> @Kartik >>>> >>>> we cant choose adjacent elements. for ex A={5,2,1,7,9,11} then we will >>>> have 5+7+11 >>>> can any one give any algo for this >>>> thank you >>>> >>>> >>>> On Mon, Aug 1, 2011 at 1:25 PM, kartik sachan >>>> <[email protected]>wrote: >>>> >>>>> oh......got it i didn't read that statement....:( >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> Abhishek Gupta >>>> MCA >>>> NIT Calicut >>>> Kerela >>>> >>>> >>> >>> >>> -- >>> Abhishek Gupta >>> MCA >>> NIT Calicut >>> Kerela >>> >>> -- >>> 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. >>> >> >> -- >> 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. >> > > > > -- > Abhishek Gupta > MCA > NIT Calicut > Kerela > > -- > 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. > -- 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.
