Sorry Dave. This doesn't do it either.
Try
100 90 2 1
13 5 2 1
The sums are
113, 103, 15, 14,
105, 95, 7, 6,
102, 92, 4, 3,
101, 91, 3, 2
So the top N=4 are
113, 105, 103, 102.
Your algorithm produces
113, 105, 102, 101.
On Oct 16, 12:26 am, Dave <dave_and_da...@juno.com> wrote:
> 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 <dave_and_da...@juno.com> 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 <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.- 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 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.
