After reading Gene's example, change my pseudocode to this:
ia = 1
ib = 1
output ia, ib, A(ia) + B(ib)
for i = 2 to n
if A(ia+1) + B(ib) > A(ia) + B(ib+1) then
ia = ia + 1
output ia, ib, A(ia) + B(ib)
else if A(ia+1) + B(ib) < A(ia) + B(ib+1) then
ib = ib + 1
output ia, ib, A(ia) + B(ib)
else // equality case
ia = ia + 1
ib = ib + 1
output ia-1, ib, A(ia-1) + B(ib)
output ia, ib-1, A(ia) + B(ib-1)
end if
end for
On Oct 15, 10:33 pm, Dave <[email protected]> wrote:
> Doesn't something like this work:
>
> ia = 1
> ib = 1
> output ia, ib, A(ia) + B(ib)
> for i = 2 to n
> if A(ia+1) + B(ib) > A(ia) + B(ib+1) then
> ia = ia + 1
> else
> ib = ib + 1
> end if
> output ia, ib, A(ia) + B(ib)
> end for
>
> Dave
>
> On Oct 14, 2:55 am, Harshal <[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.
>
> > --
> > Harshal Choudhary,
> > III Year B.Tech Undergraduate,
> > Computer Engineering Department,
> > National Institute of Technology Surathkal, Karnataka
> > India.- Hide quoted text -
>
> - Show quoted text -
--
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.
