My guess is O(n) time bound can only be achieved with Dynamic Programming here. Though, still to get proper sub problems to solve. Calling out to Dynamic Programming experts to crack this one.
On Sep 1, 4:25 pm, bharatkumar bagana <[email protected]> wrote: > @Mac: It gives us the first largest pair but need not all n pairs .. > ex: > A=1 1 3 4 > B=1 2 3 4 > pairs : (4,4),(4,3),(3,3),(2,4) ..... > > > > > > > > > > On Thu, Sep 1, 2011 at 4:57 AM, MAC <[email protected]> wrote: > > since its sorted , cant we just take last (largest if assedning) elements > > of each and return o(1) .. (since +ve we can do so i guess) > > > On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta <[email protected]>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 > > >> -- > >> 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. > > > -- > > thanks > > --mac > > > -- > > 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. > > -- > > **Please do not print this e-mail until urgent requirement. Go Green!! > Save Papers <=> Save Trees > *BharatKumar Bagana* > **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> > * > Mobile +91 8056127652* > <[email protected]> -- 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.
