Given an array arr of size n. The task is to choose k numbers from the array such that the absolute difference between the sum of chosen numbers and the sum of remaining numbers is maximum. 
Example 1:
Input:
n = 5, k = 2
arr[] = {8, 4, 5, 2, 10}
Output: 17
Explanation: If we select 2 and 4,
then abs((2+4) - (8+5+10)) = 17.
Example 2:
Input:
n = 8, k = 3
arr[] = {1, 1, 1, 1, 1, 1, 1, 1}
Output: 2
Explanation:
We can select any 3 1's.
Your Task:
You don't need to read input or print anything. Your task is to complete the function solve() which takes the array of integers arr, n and k as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(n*Logn)
Expected Auxiliary Space: O(1)
Constraints:
1 <= k <= n <=10^{5}
1 <= arr[i] <= 10^{6}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(n*Logn)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3







class Solution:

    def solve(self, arr, n, k):

        # code here

Solutions:
class Solution:

	def solve(self, arr, n, k):
		chosen_first = 0
		chosen_last = 0
		total = 0
		arr.sort()
		for num in arr:
			total += num
		for num in arr[0:k]:
			chosen_first += num
		for num in arr[n - k:]:
			chosen_last += num
		x = abs(total - chosen_first - chosen_first)
		y = abs(total - chosen_last - chosen_last)
		if x >= y:
			return x
		else:
			return y


class Solution:

	def solve(self, a, n, k):
		arr.sort(reverse=True)
		s = 0
		for i in range(0, n - k):
			s = s + arr[i]
		p = sum(arr) - s
		x = abs(s - p)
		g = 0
		for j in range(0, k):
			g = g + arr[j]
		l = sum(arr) - g
		y = abs(g - l)
		return max(x, y)


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		a = sum(arr[:])
		b = sum(arr[:k])
		c = sum(arr[n - k:])
		return max(abs(b - (a - b)), abs(c - (a - c)))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		s1 = 0
		s2 = 0
		s3 = 0
		s4 = 0
		for i in range(k):
			s1 += arr[i]
		for i in range(k, n, 1):
			s2 += arr[i]
		for i in range(n - 1, n - k - 1, -1):
			s3 += arr[i]
		for i in range(n - k - 1, -1, -1):
			s4 += arr[i]
		return max(abs(s1 - s2), abs(s3 - s4))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		summa = sum(arr)
		return max(abs(summa - 2 * sum(arr[:k])), abs(summa - 2 * sum(arr[-k:])))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		s = sum(arr[n - k:])
		ss = sum(arr[:n - k])
		return max(abs(sum(arr[n - k:]) - sum(arr[:n - k])), abs(sum(arr[k:]) - sum(arr[:k])))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		a = abs(sum(arr[:k]) - sum(arr[k:]))
		b = abs(sum(arr[n - k:]) - sum(arr[:n - k]))
		return a if a > b else b


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		if n // 2 < k:
			first_sum = sum(arr[n - k:])
			second_sum = sum(arr[:n - k])
		else:
			first_sum = sum(arr[:k])
			second_sum = sum(arr[k:])
		return abs(first_sum - second_sum)


class Solution:

	def solve(self, arr, n, k):
		arr1 = sorted(arr)
		arr2 = sorted(arr)[::-1]
		a1 = abs(sum(arr1[:k]) - sum(arr1[k:]))
		b1 = abs(sum(arr2[:k]) - sum(arr2[k:]))
		return max(a1, b1)


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		n = sum(arr)
		n1 = sum(arr[:k])
		arr.sort(reverse=True)
		n2 = sum(arr[:k])
		return max(abs(n1 - (n - n1)), abs(n2 - (n - n2)))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		s1 = sum(arr[:k])
		s2 = sum(arr[k:])
		d1 = abs(s2 - s1)
		s3 = sum(arr[-k:])
		s4 = sum(arr[:-k])
		d2 = abs(s4 - s3)
		d = max(d1, d2)
		return d


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		sum_k = 0
		sum_r = 0
		if k <= n // 2:
			for i in range(n):
				if i < k:
					sum_k += arr[i]
				else:
					sum_r += arr[i]
		else:
			for i in range(n):
				if i < n - k:
					sum_k += arr[i]
				else:
					sum_r += arr[i]
		return abs(sum_k - sum_r)


class Solution:

	def solve(self, arr, n, k):
		s = 0
		arr.sort(reverse=True)
		for i in range(k):
			s += arr[i]
		for i in range(k, n):
			s -= arr[i]
		ans = s
		s = 0
		arr.sort()
		for i in range(k):
			s += arr[i]
		for i in range(k, n):
			s -= arr[i]
		return max(abs(ans), abs(s))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		s = sum(arr)
		s1 = sum(arr[:k])
		arr.sort(reverse=True)
		s2 = sum(arr[:k])
		return max(abs(s1 - (s - s1)), abs(s2 - (s - s2)))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		i = abs(sum(arr[:k]) - sum(arr[k:]))
		arr.sort(reverse=True)
		j = abs(sum(arr[:k]) - sum(arr[k:]))
		return max(i, j)


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		l = sum(arr)
		h = sum(arr[:k])
		arr.sort(reverse=True)
		q = sum(arr[:k])
		return max(abs(h - (l - h)), abs(q - (l - q)))


class Solution:

	def solve(self, arr, n, k):
		arr.sort(reverse=True)
		s = 0
		for i in range(0, n - k):
			s += arr[i]
		p = sum(arr) - s
		rem = abs(s - p)
		g = 0
		for j in range(0, k):
			g += arr[j]
		rem_s = sum(arr) - g
		y = abs(rem_s - g)
		return max(rem, y)


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		total = sum(arr)
		max_sum = 0
		sum_low = sum(arr[:k])
		diff_low = abs(sum_low - abs(total - sum_low))
		sum_high = sum(arr[:-(k + 1):-1])
		diff_high = abs(sum_high - abs(total - sum_high))
		return max(diff_low, diff_high)


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		c = abs(sum(arr[k:]) - sum(arr[:k]))
		d = abs(sum(arr[n - k:]) - sum(arr[:n - k]))
		return max(c, d)


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		return max(abs(sum(arr[:k]) - sum(arr[k:])), abs(sum(arr[n - k:]) - sum(arr[:n - k])))
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, k) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ans = Solution().solve(arr, n, k)
		print(ans)
		tc -= 1


class Solution:

	def solve(self, arr, n, k):
		arr.sort(reverse=True)
		s = 0
		for i in range(0, n - k):
			s = s + arr[i]
		p = sum(arr) - s
		x = abs(s - p)
		g = 0
		for j in range(0, k):
			g += arr[j]
		l = sum(arr) - g
		y = abs(g - l)
		return max(x, y)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, k) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ans = Solution().solve(arr, n, k)
		print(ans)
		tc -= 1


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		sumf = 0
		suml = 0
		su = 0
		for i in range(k):
			sumf += arr[i]
			suml += arr[n - 1 - i]
		for i in arr:
			su += i
		return max(abs(sumf - (su - sumf)), abs(suml - (su - suml)))


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		if k <= n // 2:
			return abs(sum(arr[0:k]) - sum(arr[k:n]))
		else:
			x = n - k
			return abs(sum(arr[0:x]) - sum(arr[x:n]))


class Solution:

	def solve(self, arr, n, k):
		s = 0
		sarr = sum(arr)
		arr.sort()
		if n >= 2 * k:
			arr = arr[:k]
			s = sum(arr)
			return sarr - 2 * s
		else:
			arr = arr[n - k:n]
			s = sum(arr)
			return 2 * s - sarr


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		chosen1 = sum(arr[0:k])
		rem1 = sum(arr[k:])
		ans1 = abs(chosen1 - rem1)
		arr.sort(reverse=True)
		chosen2 = sum(arr[0:k])
		rem2 = sum(arr[k:])
		ans2 = abs(chosen2 - rem2)
		if ans1 > ans2:
			return ans1
		else:
			return ans2


class Solution:

	def solve(self, arr, n, k):
		arr.sort()
		a = arr[::-1]
		(suml, sumr, sumll, sumrr) = (0, 0, 0, 0)
		for i in range(k):
			suml = suml + a[i]
			sumll = sumll + arr[i]
		for i in range(k, n):
			sumr = sumr + a[i]
			sumrr = sumrr + arr[i]
		return max(abs(suml - sumr), abs(sumll - sumrr))