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 <hc4...@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.
>
> --
> Harshal Choudhary,
> III Year B.Tech Undergraduate,
> Computer Engineering Department,
> National Institute of Technology Surathkal, Karnataka
> India.
--
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.
