Maximum Sum With Specific Difference
You are given an array of integers and a number ‘K’. You can pair two elements in the array 'ARR' if the absolute difference between them is strictly less than ‘K’. Your task is to find the maximum possible sum of disjoint pairs among all the pairs of numbers you can obtain.

The sum of a pair is the sum of the elements in the pair.

For Example:

Input: ARR[] = {3, 5, 10, 15, 17, 12, 9}, K = 4 Output: 62 Then disjoint pairs with the absolute difference less than K are (3, 5), (10, 12), (15, 17) So maximum sum which we can get is 3 + 5 + 12 + 10 + 15 + 17 = 62

Note:

Note that an alternate way to form disjoint pairs is, (3, 5), (9, 12), (15, 17), but this pairing produces a lesser sum.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. The first line of each test contains an integer 'N', denoting the size of the array 'ARR' which would be given. The next line is the given array values in a space-separated set of ‘N’ elements. The last line of every test case is s single integer denoting ‘K’.

Output format:

For every test case, you need to print the maximum possible sum of disjoint pairs. Output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Maximum Sum With Specific Difference

You are given an array of integers and a number ‘K’. You can pair two elements in the array 'ARR' if the absolute difference between them is strictly less than ‘K’. Your task is to find the maximum possible sum of disjoint pairs among all the pairs of numbers you can obtain.

The sum of a pair is the sum of the elements in the pair.

For Example:

Input: ARR[] = {3, 5, 10, 15, 17, 12, 9}, K = 4
Output: 62

Then disjoint pairs with the absolute difference less than K are 
(3, 5), (10, 12), (15, 17)  
So maximum sum which we can get is 3 + 5 + 12 + 10 + 15 + 17 = 62

Note:

Note that an alternate way to form disjoint pairs is, (3, 5), (9, 12), (15, 17), but this pairing produces a lesser sum.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run.

The first line of each test contains an integer 'N', denoting the size of the array 'ARR' which would be given.

The next line is the given array values in a space-separated set of ‘N’ elements.

The last line of every test case is s single integer denoting ‘K’.

Output format:

For every test case, you need to print the maximum possible sum of disjoint pairs. 

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 3000
1 <= ARR[i] <=1000
1 <= K < 1000

Time limit: 1 sec

Accepted Answer

Sorting

Approach: We sort the given array in increasing order. For every element, we try to pair it with its previous element first. Since the array is sorted, the value of ‘ARR[i]’ would be more than ‘ARR[i - 1]’. We need to pair with a difference less than ‘K’, which means if 'ARR[i - 2]' can be paired, then ‘ARR[i - 1]’ can also be paired in a sorted array. Here, we prefer the previous element so that if ‘ARR[i]’ - ‘ARR[i - 1]’ < 'K', then definitely the previous element would give us a bigger sum as the array is sorted. Now observing the above facts, we can formulate our dynamic programming solution as follows:

Let ‘DP[i]’ denote the maximum disjoint pair sum we can achieve using first ‘i’ elements of the array. Assume currently we are at ith position, then there are two possibilities for us.

Pair up i with (i - 1)th element, i.e. DP[i] = DP[i - 2] + ARR[i] + ARR[i - 1]

or don't pair up, i.e. DP[i] = DP[i - 1]

Now, taking advantage of the above strategy, our dynamic programming solution can be as given below:

Steps:

Let ‘DP[i]’ denote the maximum disjoint pair sum we can achieve using the first ‘i’ elements of the array. Now, assume that currently, we are at the ith position, first give the previous value to ‘DP[i]’ (i.e. ‘DP[i]' = ‘DP[i - 1]’) and if the difference between the adjacent array then to maximize ‘DP[i]’ we can take one of the two possibilities for us.
We can either pair up ‘i’ with (i - 1)th element, i.e.
- ‘DP[i]’ = max('DP[i]', ‘DP[i-2] + ARR[i] + ARR[i - 1]')
Or either don't pair up, i.e.
- ‘DP[i]’ = max('DP[i]', ‘ARR[i] + ARR[i - 1]’)
Now, We return the last element in the dp array i.e. ‘DP[N - 1]’, which now contains the maximum sum of the disjoint pairs having a difference less than ‘K’ i.e.
- return ‘DP[N - 1]’.

Space Complexity: O(n)Explanation:

O(N), where N is the number of elements of the array.

Since a dp array of size ‘N’ is used to keep track of the maximized sum of ith elements in every iteration, therefore, space of O(N) would be required.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where ‘N’ is the number of elements present in the array.

Now, since they are sorted which takes O(N * log(N)) while the above iteration takes O(N) time, therefore, the total time complexity of the solution will be O(N * log(N))

Python (3.5)

'''
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    Where 'N' is the size of the array.
'''

def maxSumPairWithDifferenceLessThanK(arr, n, k):

    arr.sort()

    # Here, 'DP[i]' denotes the maximum disjoint pair sum we can achieve using first 'i' elements.
    dp = [0] * n
    
    for i in range(1, n):
    
        # First give previous value to 'DP[i]' i.e. no pairing with (i - 1)th element.
        dp[i] = dp[i - 1]

        # If current and previous element can form a pair.
        if (arr[i] - arr[i - 1] < k):
        
            # Ipdate 'DP[i]' by choosing maximum between pairing and not pairing.
            if (i >= 2):
                dp[i] = max(dp[i], dp[i - 2] + arr[i] + arr[i - 1])
            else:
                dp[i] = max(dp[i], arr[i] + arr[i - 1])
        
    return dp[n - 1]

C++ (g++ 5.4)

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    Where 'N' is the size of the array.
*/

int maxSumPairWithDifferenceLessThanK(vector& arr, int n, int k){

    sort(arr.begin(), arr.end());

    // Here, 'DP[i]' denotes the maximum disjoint pair sum we can achieve using first 'i' elements.
    int dp[n] = {0};

    for(int i = 1; i < n; i++){

        // First give previous value to 'DP[i]' i.e. no pairing with (i - 1)th element.
        dp[i] = dp[i - 1];

        // If current and previous element can form a pair.
        if(arr[i] - arr[i - 1] < k){

            // Update 'DP[i]' by choosing maximum between pairing and not pairing.
            if(i >= 2){
                dp[i] = max(dp[i], dp[i - 2] + arr[i] + arr[i - 1]);
            }
            else{
                dp[i] = max(dp[i], arr[i] + arr[i - 1]);
            }
        }
    }

    return dp[n - 1];
}

Java (SE 1.8)

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    Where 'N' is the size of the array.
*/

import java.util.Arrays;

public class Solution {
    public static int maxSumPairWithDifferenceLessThanK(int[] arr, int n, int k) {
        
        Arrays.sort(arr);

        // Here, 'DP[i]' denotes the maximum disjoint pair sum we can achieve using first 'i' elements.
        int[] dp = new int[n];

        for(int i = 1; i < n; i++){

            // First give previous value to 'DP[i]' i.e. no pairing with (i - 1)th element.
            dp[i] = dp[i - 1];

            // If current and previous element can form a pair.
            if(arr[i] - arr[i - 1] < k){

                // Update 'DP[i]' by choosing maximum between pairing and not pairing.
                if(i >= 2){
                    dp[i] = Math.max(dp[i], dp[i - 2] + arr[i] + arr[i - 1]);
                }
                else{
                    dp[i] = Math.max(dp[i], arr[i] + arr[i - 1]);
                }
            }
        }

        return dp[n - 1];
    }
}

Accepted Answer

Optimized Sorting Approach

Approach: We can sort the array to ensure that every i’th and (i-1)st element is the closest possible pair. Now to get the maximum possible sum, we can iterate from largest to smallest, giving larger numbers priority over smaller numbers.

Algorithm:

Sort all the elements present inside the array. Initialize ‘MAXSUM' to 0.
Now for each ‘i’ from ‘N’ - 1 to 1:
- If the difference of ‘ARR[i]’ and ‘ARR[i - 1]’ is less than ‘K’, then add the pair to the ‘MAXSUM'.
If the difference between ‘ARR[i]’ and ‘ARR[i - 1]’ is not less then ‘K’, we continue our iteration.
We finally return ‘MAXSUM'.

Space Complexity: O(1)Explanation:

O(1)

As Constant space is used.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where ‘N’ is the number of elements present in the array.

Now, since they are sorted which takes O(N * log(N)) while the above iteration takes O(N) time, therefore, the total time complexity of the solution will be O(N * log(N)).

Java (SE 1.8)

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(1)

    Where 'N' is the size of the array.
*/

import java.util.Arrays;

public class Solution {
    public static int maxSumPairWithDifferenceLessThanK(int[] arr, int n, int k) {
        // Initialize 'MAXSUM' to 0.
        int maxSum = 0;

        // Sort all the elements present inside the array.
        Arrays.sort(arr);

        int i = n - 1;

        while(i > 0){
            /*
                If the difference of 'ARR[i]' and 'ARR[i - 1]' is less than 'K', 
                then add the pair to the 'MAXSUM'.
            */
            if(arr[i] - arr[i - 1] < k){
                maxSum += arr[i];
                maxSum += arr[i - 1];
                i -= 1;
            }
            
            i -= 1;
        }

        return maxSum;
    }
}

Python (3.5)

'''
    Time Complexity: O(N * log(N))
    Space Complexity: O(1)

    Where 'N' is the size of the array.
'''

def maxSumPairWithDifferenceLessThanK(arr, n, k):

    # Initialize 'MAXSUM' to 0.
    maxSum = 0

    # Sort all the elements present inside the array.
    arr.sort()

    i = n - 1

    while (i > 0):

        '''
            If the difference of 'ARR[i]' and 'ARR[i - 1]' is less than 'K', 
            then add the pair to the 'MAXSUM'.
        '''
        if (arr[i] - arr[i - 1] < k):
            maxSum += arr[i]
            maxSum += arr[i - 1]
            i -= 1

        i -= 1

    return maxSum

C++ (g++ 5.4)

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(1)

    Where 'N' is the size of the array.
*/

int maxSumPairWithDifferenceLessThanK(vector & arr, int n, int k){

    // Initialize 'MAXSUM' to 0.
    int maxSum = 0;

    // Sort all the elements present inside the array.
    sort(arr.begin(), arr.end());

    int i = n - 1;

    while(i > 0){
        /*
            If the difference of 'ARR[i]' and 'ARR[i - 1]' is less than 'K', 
            then add the pair to the 'MAXSUM'.
        */
        if(arr[i] - arr[i - 1] < k){
            maxSum += arr[i];
            maxSum += arr[i - 1];
            i -= 1;
        }
        
        i -= 1;
    }

    return maxSum;
}

You are given an array of integers and a number ‘K’. You can pair two elements in the array 'ARR' if the absolute difference between them is strictly less than ‘K’. Your task is to find the maximum possible sum of disjoint pairs among all the pairs of numbers you can obtain.

The sum of a pair is the sum of the elements in the pair.

For Example:

Note:

Input format:

Output format:

Note:

Constraints:

Top American Express Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in American Express Software Developer