# N Max Pair Combinations

Given two arrays *A* and *B* of size *N* each, find the maximum *N* elements from the sum combination *(A[i]+B[j])* formed elements *A* and *B*. You can only combine elements of two arrays you can't combine the same array elements.

**Problem Description:**

The problem wants you to use two arrays as given and find the maximum sum that you can get from both the arrays such that the pair elements belong to 1st and 2nd array, keeping in mind that you cannot use the same array elements it will be against the problem statement i.e., if you are using *a[i]* and *b[j]* then they belong to two arrays respectively.

**Input:** The first line of the input consists of *T* number of test cases. Each test case consists of *N* size of the array. Followed by two lines are array *A* and *B* respectively.

**Output:** Print the maximum *N* elements after combining from both the arrays in a separate line for each test case.

**Example:**

Input:
T = 1
N = 4
[1,4,2,3]
[2,5,1,6]
Output:
10, (4+6)
9, (3+6)
9, (4+5)
8, (2+6)
All the above elements are the n pairs
with maximum sum that we can obtain.

(1) Brute Force Approach:In this approach, we will use a two-loop and iterate through all combinations of the elements and store them in a heap or a vector. If we are storing them in a max heap then we pop the top element from the heap n times since the top of the heap is the maximum sum elements and if we are storing sum combination in vector then we need to sort the vector and then we take n max sum combination from it.

The above logic can be implemented with the help of vector and priority_queue that is a heap data structure.

O(n*n)O(n*n)Program:Output:(2) Better Approach:In this approach, we will use the priority queue with pairs and set for managing the indices that we have used that are remaining. We need to sort both the arrays and store their last elements in the max heap which we create with help of priority_queue and pairs.

priority_queue<pair<int, pair<int, int>>> heap, the first pair consists of sum and another pair for indices from which the sum has been obtained. To avoid the duplicacy of array elements we will use either a map or set with pairs. We need to repeat the process n times to get the maximum sum pairs, in each step we will check the indices pair{l,r-1}and{l-1,r}for storing it in the heap after processing the previous indices{l,r}.O(Nlog(N)O(N)Program:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: