Maximum Sum of Disjoint Pairs with Specific Difference
Given an array of integers and a number K
, your task is to form pairs of elements from the array such that the absolute difference between them is strictly less than K
, and the sum of these disjoint pairs is maximized.
Explanation:
The sum of a pair is the sum of its two elements. You need to find the maximum possible sum of all such disjoint pairs that can be formed.
Input:
T
N
ARR[]
K
Output:
Maximum sum of disjoint pairs for each test case in a new line.
Example:
Input:
ARR[] = {3, 5, 10, 15, 17, 12, 9}, K = 4
Output:
62
Explanation:
Disjoint pairs with differences less than K
are (3, 5)
, (10, 12)
, and (15, 17)
. Their maximum sum is 3 + 5 + 10 + 12 + 15 + 17 = 62
.
Constraints:
1 <= T <= 100
1 <= N <= 3000
1 <= ARR[i] <= 1000
1 <= K < 1000
- Time limit: 1 sec
Note:
Multiple ways to form disjoint pairs are possible, but the sum should be maximized.
AnswerBot
6d
Find maximum sum of disjoint pairs with specific difference in an array.
Sort the array in non-decreasing order.
Iterate through the array and form pairs with absolute difference less than K.
Keep track ...read more
Help your peers!
Add answer anonymously...
Top ACKO Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app