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 <[email protected]>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 <[email protected]> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[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.
