@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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
