Please see *stable merge *in question. On Sun, Jul 15, 2012 at 2:04 AM, sengar.mahi <sengar.m...@gmail.com> wrote:
> @naveen : 3*7+2*9+1*3 =42 is not maximum.. > sum of the product would me maximum wen, i guess, most weighted elements > are adjacent > like in this case > if c={1,2,3,3,7,9} > 1*2 + 3*3 + 7*9=74 (maximum ) > > thus this question is just merging both strings such resultant (here C) is > in sorted order which can be easily done in nlogn . > > > On Sat, Jul 14, 2012 at 2:15 PM, Navin Gupta <navin.nit...@gmail.com>wrote: > >> As the final array contains element in stable-order, at any time we have >> 3 options for choosing the elements from A & B. >> 1- A[i] & A[i+1] >> 2- A[i] & B[I] >> 3- B[i] & B[i+1] >> we will choose that pair whose product is maximum. >> For ex:- >> A-2,1,3 >> B-3,7,9 >> C- 3,7,2,9,1,3 >> Its a linear time solution with constant time complexity. >> Algo :- >> 1 - Keep two indexes i=0 and j=0 pointing to arrays A & B respectively >> and k=0 for array C. >> 2 - Now , check the maximum of (a[i]*a[i+1], a[i]*b[j], b[j]*b[j+1] ). >> 3 - If a[i]*a[i+1] is maximum, add a[i],a[i+1] to C, i+=2. >> 4 - If a[i]*b[j] is maximum, add a[i],b[j] to C, i++,j++. >> 5 - If b[j]*b[j+1] is maximum, add b[j],b[j+1] to C, j+=2. >> 6 - k+=2. >> 7 - If i,j reached end, then break else Goto step 2. >> Time Complexity :- O(n) >> Space Complexity :- O(1) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/6-JIwC7l-hYJ. >> >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > *Regards* > Mahendra Pratap Singh Sengar > B-tech 4/4 > NIT Warangal. > > Facebook ID <http://www.facebook.com/mkingmahi> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.