Python program to find maximum difference between two subsets of m elements

In this tutorial, we will calculate the maximum difference between two subsets of an array in Python.

To calculate the max difference between two subsets of an array of length n, we need to obtain two subsets of length m such that the difference of the sum of elements of subsets is maximum. To obtain the maximum difference between subsets, we need subsets such that one subset has the highest sum and another has the lowest sum.

A subset of length m will have the highest sum if it has the m largest elements of the array. Similarly, a subset with the lowest sum is obtained by adding the smallest m elements of the array. So, we apply sort() on the given array, add first m elements, and last m elements.

We subtract both sums to get the maximum difference. The difference is then returned.

Input: a = [3,1,7,9,5], m = 3
Output: 12
Sorting gives [1,3,5,7,9] and 
Maximum Sum is (9+7+5) = 21, Minimum sum is (1+3+5) = 9
21 - 9 = 12

Input: a = [31,22,1,5,12,45], m = 2
Output: 70
Sorting gives [1,5,12,22,31,45] and (45+31)-(1+5) = 70

To find maximum difference between two subsets of m elements

def find_max_difference(arr, n, m): 
  max_sum = 0
  min_sum = 0
  
  # sort array 
  arr.sort() 
  j = n-1
  for i in range(m): 
    min_sum += arr[i] 
    max_sum += arr[j] 
    j = j - 1
  
  return(max_sum - min_sum)

# Driver code 
if __name__ == "__main__": 
  arr = [31, 22, 1, 5, 12, 45]
  n = len(arr) 
  m = int(input("Enter the length of subset: "))

  print(find_max_difference(arr, n, m))

Output:
Enter the length of subset: 2
70

Also Read: Python program to get all subsets of set using Loops and Functions

Thank You for Reading and Keep Learning 🙂