@Don: It is more complicated than that.
1st pair: (A(n),B(n)).
2nd pair: Either (A(n-1),B(n)) or (A(n),B(n-1)).
Suppose the 2nd pair is (A(n-1),B(n)).
3rd pair: Either (A(n-2),B(n)) or (A(n),B(n-1)).
Suppose the 3rd pair is (A(n),B(n-1)).
4th pair: Can be any of (A(n-2),B(n)), (A(n-1),B(n-1)), and
(A(n),B(n-2)).
Every unused pair that is the first unused pair in both its row and
column is eligible. When you have chosen n-1 pairs, there can be
O(sqrt(n)) candidates for the last choice. To me, this says that you
must keep the eligible candidates in some data structure. To choose a
pair, you must search the data structure for the largest sum. When you
have chosen a pair, you must update the data structure to remove the
chosen pair, check each of the two neighbors to see if it already in
the data structure, and add any not already in the structure to the
structure. Doing all of this n times with O(n) work seems unlikely to
me. I hypothesize that the best you can do it in is O(n log n). I
think a balanced binary search tree might be appropriate, since each
of these operations can be performed in O(log(size of tree)).
I'd love for someone to prove me wrong by demonstrating an O(n)
solution.
Dave
On Sep 1, 9:55 am, Don <dondod...@gmail.com> wrote:
> Start with pair (A(i), B(j)) where i and j are both n.
> Then the next largest pair will either be (A(i-1), B(n)) or (A(n),
> B(j-1)). Whichever sum is larger, set i and j to those values. Repeat
> as desired.
>
> Don
>
> On Sep 1, 3:45 am, Navneet Gupta <navneetn...@gmail.com> wrote:
>
>
>
> > Given two sorted positive integer arrays A(n) and B(n), we define a
> > set S = {(a,b) | a in A and b in B}. Obviously there are n2 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. need an O(n)
> > algorithm.
>
> > --
> > Regards,
> > Navneet- 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 algogeeks@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.
