# Maximum difference between two subsets of m elements

Given an array of n integers and a number m, find the maximum possible difference between two sets of m elements chosen from given array.

Examples:

```Input : arr[] = 1 2 3 4 5
m = 4
Output : 4
The maximum four elements are 2, 3,
4 and 5. The minimum four elements are
1, 2, 3 and 4. The difference between
two sums is (2 + 3 + 4 + 5) - (1 + 2
+ 3 + 4) = 4

Input : arr[] = 5 8 11 40 15
m = 2
Output : 42
The difference is (40 + 15) - (5  + 8)
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to first sort the array, then find sum of first m elements and sum of last m elements. Finally return difference between two sums.

## CPP

 `// C++ program to find difference ` `// between max and min sum of array ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `// utility function ` `int` `find_difference(``int` `arr[], ``int` `n, ``int` `m) ` `{ ` `    ``int` `max = 0, min = 0; ` ` `  `    ``// sort array ` `    ``sort(arr, arr + n); ` ` `  `    ``for` `(``int` `i = 0, j = n - 1; ` `         ``i < m; i++, j--) { ` `        ``min += arr[i]; ` `        ``max += arr[j]; ` `    ``} ` ` `  `    ``return` `(max - min); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = { 1, 2, 3, 4, 5 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``int` `m = 4; ` `    ``cout << find_difference(arr, n, m); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find difference ` `// between max and min sum of array ` `import` `java.util.Arrays; ` ` `  `class` `GFG { ` `    ``// utility function ` `    ``static` `int` `find_difference(``int` `arr[], ``int` `n, ` `                               ``int` `m) ` `    ``{ ` `        ``int` `max = ``0``, min = ``0``; ` ` `  `        ``// sort array ` `        ``Arrays.sort(arr); ` ` `  `        ``for` `(``int` `i = ``0``, j = n - ``1``; ` `             ``i < m; i++, j--) { ` `            ``min += arr[i]; ` `            ``max += arr[j]; ` `        ``} ` ` `  `        ``return` `(max - min); ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `main(String arg[]) ` `    ``{ ` `        ``int` `arr[] = { ``1``, ``2``, ``3``, ``4``, ``5` `}; ` `        ``int` `n = arr.length; ` `        ``int` `m = ``4``; ` `        ``System.out.print(find_difference(arr, n, m)); ` `    ``} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python3

 `# Python program to ` `# find difference  ` `# between max and ` `# min sum of array ` ` `  `def` `find_difference(arr, n, m): ` `    ``max` `=` `0``; ``min` `=` `0` `      `  `    ``# sort array  ` `    ``arr.sort(); ` `    ``j ``=` `n``-``1`  `    ``for` `i ``in` `range``(m): ` `        ``min` `+``=` `arr[i] ` `        ``max` `+``=` `arr[j] ` `        ``j ``=` `j ``-` `1` `      `  `    ``return` `(``max` `-` `min``) ` `  `  `# Driver code ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``arr ``=` `[``1``, ``2``, ``3``, ``4``, ``5``] ` `    ``n ``=` `len``(arr) ` `    ``m ``=` `4` ` `  `    ``print``(find_difference(arr, n, m))    ` ` `  `# This code is contributed by ` `# Harshit Saini `

## C#

 `// C# program to find difference ` `// between max and min sum of array ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// utility function ` `    ``static` `int` `find_difference(``int``[] arr, ``int` `n, ` `                                          ``int` `m) ` `    ``{ ` `        ``int` `max = 0, min = 0; ` ` `  `        ``// sort array ` `        ``Array.Sort(arr); ` ` `  `        ``for` `(``int` `i = 0, j = n - 1; ` `            ``i < m; i++, j--) { ` `            ``min += arr[i]; ` `            ``max += arr[j]; ` `        ``} ` ` `  `        ``return` `(max - min); ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] arr = { 1, 2, 3, 4, 5 }; ` `        ``int` `n = arr.Length; ` `        ``int` `m = 4; ` `        ``Console.Write(find_difference(arr, n, m)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal `

## PHP

 ` `

Output:

```4
```

We can optimize the above solution using more efficient approaches discussed in below post.
k largest(or smallest) elements in an array | added Min Heap method

## tags:

Arrays Heap Searching Arrays Searching Heap