Given two arrays A & B of size N each.
Find the maximum n elements from the sum combinations (Ai + Bj) formed from elements in array A and B.
For example if A = [1,2], B = [3,4], then possible pair sums can be 1+3 = 4 , 1+4=5 , 2+3=5 , 2+4=6
and maximum 2 elements are 6, 5
Example:
N = 4
a[]={1,4,2,3}
b[]={2,5,1,6}
Maximum 4 elements of combinations sum are
10 (4+6),
9 (3+9),
9 (4+5),
8 (2+6)
Sort both array A and B.
Now insert maximum pair i.e. (An , Bn, |An - Bn|) pair in heap(max Heap)
on each iteration extract max pair from heap let call it (Ai, Bj, |Ai - Bj|)
insert pair (Ai, Bj-1, |…|) and (Ai-1, Bj, |…|) in heap.
This way you can iterate on max pair
Time complexity O(nlogN)
Along with what @aya_cool
said, Instead of Heap you could use Priority Queue and also keep in mind the number of insertions since it is a costly operation, this can be done by keeping a map in check of the numbers which are already present in the PriorityQueue. Or you could use Some Data Structures like TreeMap in Java, in case you do in Java. TreeMap is a combination of HashMap and sorted Keys based on Custom Comparator (might be ascending or descending here in case descending). Hope it helps…
Actually priority queue is an abstract data structure, which is usually implemented as a heap. So using a priority queue instead of a heap does not make sense.
Yes, i understand that 
I meant as in inbuilt Data Structure i.e. STL Container Adapter std::priority_queue. Even Tree Map uses RB Tree, for implementation, that’s what i was trying to point out. But where efficiency matters, you wont prefer writing whole MaxHeapify functions.
Ah I get you now. Yes, of course, using stl is preferable to implementing one’s own heap
How would we implement this in Java since we don’t have “pair” in Java ?
you can make a class named Pair
class Pair{
int x,y;
}
which pair is aya_cool taking about. He’s saying pair but writing 3 terms. Which two form the pair? And how to get the sum?
By pair I suppose @aya_cool meant pair<int, pair<int, int>>, and I realize now that his solution is actually not correct.
First, sort the arrays A and B. Then initialize a max heap with the tuple (A[n-1]+B[n-1],\ n,\ n). You can use a priority_queue in C++ and a TreeMap in Java as @ssaxena36 has said. The heap should be ordered by the first value, the order of the rest does not matter. Then pop the heap to get the current largest sum and the indices of the elements in A and B which make up this sum. Let this popped tuple be (sum,\ i,\ j). Next insert (A[i]+B[j-1],\ i,\ j-1) and (A[i-1]+B[j],\ i-1,\ j) into the heap. Repeat this procedure n times to get the n largest sums.