@Mohit
according to ur algo if a[1], b[0] has sum greater than a[0],b[1]
then i is incremented i is now 2 so for next iteration u ll compare a[2]
b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever. think
for ths case also.
On 2 May 2010 11:22, mohit ranjan <shoonya.mo...@gmail.com> wrote:
> @Algoose Chase
>
> point taken
> Thanks
>
>
> Mohit Ranjan
> Samsung India Software Operations.
>
>
> On Sat, May 1, 2010 at 8:43 PM, Algoose Chase <harishp...@gmail.com>wrote:
>
>> @mohit
>>
>> The idea of DP is fine.
>> When you find the Max i dont think you need to include A[i+1]+B[j+1]
>> because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] since
>> both the lists are sorted in decreasing order.
>>
>>
>> On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan <shoonya.mo...@gmail.com>wrote:
>>
>>> oops
>>>
>>> Sorry didn't read properly
>>> last algo was for array sorted in ascending order
>>>
>>> for this case, just reverse the process
>>>
>>>
>>> A[n] and B[n] are two array
>>>
>>> loop=n, i=0, j=0;
>>>
>>>
>>> while(loop>0) // for n largest pairs
>>> {
>>> print A[i]+B[j]; // sum of first index from both array will be
>>> max
>>>
>>> foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using DP,
>>> moving forward
>>>
>>> if foo==A[i+1]+B[j]; i++ // only increment A
>>> if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
>>> if foo==A[i]+B[j+1]; j++ // increment only B
>>>
>>> }
>>>
>>>
>>>
>>> Mohit Ranjan
>>> Samsung India Software Operations.
>>>
>>>
>>> On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan
>>> <shoonya.mo...@gmail.com>wrote:
>>>
>>>> Hi Divya,
>>>>
>>>>
>>>> A[n] and B[n] are two array
>>>>
>>>> loop=n, i=n-1, j=n-1;
>>>>
>>>> while(loop>0) // for n largest pairs
>>>> {
>>>> print A[i]+B[j]; // sum of last index from both array will be
>>>> max
>>>>
>>>> foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using DP
>>>> moving backward
>>>>
>>>> if foo=A[i-1]+B[j]; i-- // only reduce A
>>>> if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
>>>> if foo=A[i]+B[j-1]; j-- // reduce only B
>>>> }
>>>>
>>>> Time: O(n)
>>>>
>>>>
>>>> Mohit Ranjan
>>>>
>>>>
>>>>
>>>> On Fri, Apr 30, 2010 at 5:35 PM, divya <sweetdivya....@gmail.com>wrote:
>>>>
>>>>> Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
>>>>> say they are decreasingly sorted), we define a set S = {(a,b) | a \in
>>>>> A
>>>>> and b \in B}. Obviously there are n^2 elements in S. The value of such
>>>>> a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
>>>>> from S with largest values. The tricky part is that we need an O(n)
>>>>> algorithm.
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
