## Introduction

For this current problem, we are given an array of elements and a value k. We need to find the maximum difference between a group of k-elements and the rest of the array for the given array. We need to first divide the array into two groups such that one group must contain k-elements and the other group must contain the rest of the array elements. The idea here is to select the best k-element group elements such that the maximum difference between this group and the group of remaining elements must be high.

Also see, __Rabin Karp Algorithm__

## Solution

### Approach

Let’s have some simple examples to understand this problem.

Example1:

Say, we are provided with an array of elements as a = [1,3,2,4,6,5], k = 2.

Then we can divide the array as g1 = [1,2] and g2 = [3,4,5,6]. Thus we get the maximum difference between these two groups will be abs(sum(g2) - sum(g1)) = 18-3, i.e15. Here the main problem is to select the best possible elements for the k-element group.

Example2:

Say, we are provided with an array of elements as a = [1, -2, -3, -1, 3], k = 2.

Then we can divide the array as g1 = [-1, -2, -3] and g2 = [1, 3]. Thus we get the maximum difference between these two groups will be abs(sum(g2) - sum(g1)) = 4- (-6), i.e 10. The main problem is selecting the best possible elements for the k-element group.

Here we can observe mainly two cases to get the optimal solution. In the first case, we can group all the k-smallest elements and the rest of the elements as another group. Similarly, in the second case, we can group all the k-largest elements and the rest of the elements as another group. So sorting the array might help us to solve the problem easily.

In this problem, we just need to print the maximum difference and not the groups. So we can follow the below algorithm:

Step1: Sort the given array.

Step2: Calculate the sum of the whole array of elements.

Step3: As discussed, find the sum of the first k-smallest elements.

Step4: calculate the difference as d1 = abs( arraySum - 2*k_Smallest_sum)

Step5: Another case, find the sum of first k-largest elements.

Step6: calculate the new difference as d2 = abs( arraySum - 2*k_largest_sum)

Step7: Finally, display the max(d1, d2) as output.

### Code

Python:

```
def calculate_sum(arr, n): #Calculating the sum of the given array up to n elements.
sum = 0
for i in range(n):
sum = sum + arr[i]
return sum
def solution(arr, k):
#Step1: Sorting the array
arr.sort()
#Step2: calculating the whole array sum
arr_total_sum = calculate_sum(arr, len(arr))
#Step3: find the sum of the first k-smallest elements.
K_smallest = calculate_sum(arr, k)
#Step4: calculate the difference as d1
d1 = abs( arr_total_sum - 2*K_smallest)
#Step5: find the sum of first k-largest elements.
K_largest = calculate_sum(arr[-k:], k)
#Step6: calculate the new difference as d2
d2 = abs( arraySum - 2*K_largest)
#Step7: Finally, display the max(d1, d2) as output.
return max(d1, d2)
arr = [1,3,2,4,6,5]
k = 2
print(solution(arr, k)
```

Output: 15

The time complexity for this python solution code is O(n).

You can find this solution in different languages by referring to this __GFG blog__.