@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.
