Please see *stable merge *in question.
On Sun, Jul 15, 2012 at 2:04 AM, sengar.mahi <[email protected]> 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 <[email protected]>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 [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*
> 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 [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.
