Maximum Sum Combination
Hard Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Maximum Sum Combination, Priority Queue, Greedy Algorithm, Sorting, Arrays, Optimization, priority queue, greedy algorithm, sorting algorithms, combinatorics, array, time complexity analysis.
Problem Statement : Given two arrays A and B of size N and an integer K, find the K maximum sum combinations from all possible combinations of elements from A and B (where each combination is a sum of one element from A and one element from B). Input Specification : First line: Integer N (size of arrays) Second line: N space separated integers (array A) Third line: N space separated integers (array B) Fourth line: Integer K Output Specification : K space separated integers in descending order representing the top K maximum sum combinations. Constraints : 1 ≤ N ≤ 10^5 1 ≤ K ≤ min(N^2, 10^5) 10^9 ≤ A[i], B[i] ≤ 10^9 Sample Input : Sample Output : Explanation : All possible sum combinations are: 1+8=9, 1+5=6, 1+3=4, 4+8=12, 4+5=9, 4+3=7, 2+8=10, 2+5=7, 2+3=5. The top 3 sums are 12, 10, and 9.