Given an array a[ ] of N elements. Consider array as a circular array i.e. element after a_{n} is a_{1}. The task is to find maximum sum of the absolute difference between consecutive elements with rearrangement of array elements allowed i.e. after any rearrangement of array elements find |a_{1} – a_{2}| + |a_{2} – a_{3}| + …… + |a_{n-1 }– a_{n}| + |a_{n} – a_{1}|.
Example 1:
Input:
N = 4
a[] = {4, 2, 1, 8}
Output: 
18
Explanation: Rearrangement done is {1, 8, 
2, 4}. Sum of absolute difference between 
consecutive elements after rearrangement = 
|1 - 8| + |8 - 2| + |2 - 4| + |4 - 1| = 
7 + 6 + 2 + 3 = 18.
Example 2:
Input:
N = 2
a[] = {10, 12}
Output: 
4
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function maxSum() that takes array a[ ] and its size N as input parameters and return the maximum sum using above method.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(1)
Constraints:
2 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Greedy algorithms

Starter code: #User function Template for python3


def maxSum(arr,n):
    # code here

Solutions:
def maxSum(arr, n):
	ans = []
	arr = sorted(arr)
	(i, j) = (0, len(arr) - 1)
	while i < j:
		ans.append(arr[i])
		ans.append(arr[j])
		i += 1
		j -= 1
	if i == j:
		ans.append(arr[i])
	final_ans = 0
	for i in range(1, len(ans)):
		final_ans += abs(ans[i] - ans[i - 1])
	final_ans += abs(ans[-1] - ans[0])
	return final_ans


def maxSum(arr, n):
	arr.sort()
	left = arr[:n // 2]
	right = arr[n // 2:][::-1]
	l = []
	for i in range(len(left)):
		l.append(left[0])
		left.pop(0)
		l.append(right[0])
		right.pop(0)
	l += left + right
	summ = 0
	for i in range(len(l) - 1):
		summ += abs(l[i] - l[i + 1])
	summ += abs(l[0] - l[-1])
	return summ


def maxSum(arr, n):
	ans = 0
	arr.sort()
	i = 0
	j = n - 1
	while i <= j:
		ans += abs(arr[i] - arr[j])
		i += 1
		j -= 1
	return ans * 2


def maxSum(arr, n):
	arr.sort()
	s1 = 0
	for i in range(n):
		s1 += abs(arr[i] - arr[-i - 1])
	return s1


def maxSum(arr, n):
	n = len(arr)
	n = len(arr)
	arr.sort()
	max_sum = 0
	for i in range(n // 2):
		max_sum += abs(arr[i] - arr[n - i - 1]) * 2
	return max_sum


def maxSum(arr, n):
	arr.sort()
	j = n - 1
	summ = 0
	for i in range(n):
		summ += abs(arr[i] - arr[j])
		j -= 1
	return summ


def maxSum(arr, n):
	arr.sort()
	b = []
	i = 0
	j = n - 1
	f = 1
	while i <= j:
		if f == 1:
			b.append(arr[i])
			i += 1
		else:
			b.append(arr[j])
			j -= 1
		f *= -1
	s = 0
	for i in range(n - 1):
		s += abs(b[i] - b[i + 1])
	s += abs(b[n - 1] - b[0])
	return s


def maxSum(arr, n):
	arr.sort()
	sum1 = 0
	for i in range(int(n / 2)):
		sum1 += abs(arr[i] - arr[-i - 1])
	return sum1 * 2


def maxSum(arr, n):
	arr.sort()
	total = 0
	for i in range(int(n / 2)):
		total -= 2 * arr[i]
		total += 2 * arr[n - i - 1]
	return total


def maxSum(arr, n):
	a = arr.copy()
	arr.sort()
	s = 0
	f = [None] * n
	a.sort(reverse=True)
	i = 0
	j = 0
	while i < n:
		f[i] = arr[j]
		if i + 1 < n:
			f[i + 1] = a[j]
		i += 2
		j += 1
	for i in range(n - 1):
		s += abs(f[i] - f[i + 1])
	s += abs(f[n - 1] - f[0])
	return s


def maxSum(arr, n):
	arr.sort()
	summy = 0
	(l, r) = (0, n - 1)
	while l < r:
		summy += arr[r] - arr[l]
		l += 1
		r -= 1
	return summy * 2


def maxSum(arr, n):
	a = []
	b = []
	arr.sort()
	a[:] = arr[:n // 2]
	b[:] = arr[n // 2:]
	b.reverse()
	k = []
	i = 0
	while len(k) < n:
		if i < len(a):
			k.append(a[i])
		if i < len(b):
			k.append(b[i])
		i = i + 1
	c = 0
	for i in range(n - 1):
		c = c + abs(k[i + 1] - k[i])
	c = c + abs(k[-1] - k[0])
	return c


def maxSum(arr, n):
	arr.sort()
	ans = 0
	start = 0
	end = n - 1
	while start < end:
		ans += abs(arr[start] - arr[end])
		start += 1
		end -= 1
	return ans * 2


def maxSum(arr, n):
	arr.sort()
	a = []
	i = 0
	j = n - 1
	while i < j:
		a.append(arr[i])
		a.append(arr[j])
		i += 1
		j -= 1
	ans = 0
	if i == j:
		a.append(arr[i])
	for i in range(len(a) - 1):
		ans += abs(a[i] - a[i + 1])
	ans += abs(a[-1] - a[0])
	return ans


def maxSum(arr, n):
	s = 0
	arr.sort(reverse=True)
	for i in range(n):
		s += abs(arr[i] - arr[-i - 1])
	return s


def maxSum(a, n):
	a.sort()
	sum1 = 0
	for i in range(n):
		sum1 += abs(a[i] - a[-i - 1])
	return sum1


def maxSum(arr, n):
	arr.sort()
	result = 0
	i = 0
	j = n - 1
	while i < j:
		result += abs(arr[i] - arr[j])
		result += abs(arr[i + 1] - arr[j])
		i += 1
		j -= 1
	result += abs(arr[i] - arr[0])
	return result


def maxSum(arr, n):
	sa = sorted(arr)
	i = 0
	j = n - 1
	ssum = 0
	ra = []
	loops = 0
	while len(ra) < n:
		ra.append(sa[i])
		ssum += abs(ra[-1] - sa[j])
		i += 1
		if len(ra) < n:
			ra.append(sa[j])
			ssum += abs(ra[-1] - sa[i])
			j -= 1
	ssum += abs(ra[0] - ra[-1])
	return ssum


def maxSum(arr, n):
	mid = n // 2
	arr.sort()
	sum = 0
	for i in range(0, mid):
		sum -= 2 * arr[i]
		sum += 2 * arr[n - 1 - i]
	return sum


def maxSum(arr, n):
	arr.sort()
	l = []
	counter = 0
	k = 0
	i = 0
	j = n - 1
	while k < n:
		if counter % 2 == 0:
			l.append(arr[i])
			i += 1
		else:
			l.append(arr[j])
			j -= 1
		counter += 1
		k += 1
	maxsum = 0
	for i in range(n - 1):
		maxsum += abs(l[i + 1] - l[i])
	maxsum += l[n - 1] - l[0]
	return maxsum


def maxSum(arr, n):
	a = sorted(arr)
	d = sorted(arr, reverse=True)
	s = 0
	for i in range(n):
		s += abs(d[i] - a[i])
	return s


import math

def maxSum(arr, n):
	arr.sort()
	sum1 = 0
	for i in range(n):
		sum1 += abs(arr[i] - arr[-i - 1])
	return sum1


def maxSum(arr, n):
	asc = sorted(arr)
	dsc = sorted(arr, reverse=True)
	s = 0
	for i in range(n):
		s += abs(asc[i] - dsc[i])
	return s


def maxSum(arr, n):
	arr = sorted(arr)
	sum = 0
	for i in range(n // 2):
		sum -= 2 * arr[i]
		sum += 2 * arr[n - 1 - i]
	return sum


def maxSum(arr, n):
	arr.sort()
	a1 = []
	a2 = []
	for i in range(n):
		if i < n // 2:
			a1.append(arr[i])
		else:
			a2.append(arr[i])
	a2 = a2[::-1]
	a3 = []
	(j, k) = (0, 0)
	for i in range(n):
		if i % 2 == 0 and j < len(a1):
			a3.append(a1[j])
			j += 1
		else:
			a3.append(a2[k])
			k += 1
	sum1 = 0
	for i in range(n - 1):
		sum1 += abs(a3[i] - a3[i + 1])
	sum1 += abs(a3[-1] - a3[0])
	return sum1


def maxSum(arr, n):
	arr.sort()
	summ = 0
	for x in range(n):
		summ += abs(arr[x] - arr[n - 1 - x])
	return summ


def maxSum(arr, n):
	newArray = arr
	sampleArray = []
	intermediateArray = newArray.sort()
	startArrayIndex = 0
	endArrayIndex = -1
	executionPeriod = n // 2
	sum = 0
	for i in range(0, executionPeriod, 1):
		sampleArray.append(newArray[startArrayIndex])
		sampleArray.append(newArray[endArrayIndex])
		startArrayIndex = startArrayIndex + 1
		endArrayIndex = endArrayIndex - 1
	if len(sampleArray) >= 2 and n % 2 == 0:
		for i in range(0, n - 1, 1):
			difference = sampleArray[i] - sampleArray[i + 1]
			if difference > 0:
				sum = sum + difference
			else:
				sum = sum - difference
		lastDifference = sampleArray[0] - sampleArray[n - 1]
		if lastDifference > 0:
			sum = sum + lastDifference
		else:
			sum = sum - lastDifference
	elif len(sampleArray) >= 2 and n % 2 != 0:
		midIndex = newArray[n // 2 + 1]
		sampleArray.append(midIndex)
		for i in range(0, n - 1, 1):
			difference = sampleArray[i] - sampleArray[i + 1]
			if difference > 0:
				sum = sum + difference
			else:
				sum = sum - difference
		lastDifference = sampleArray[0] - sampleArray[n - 1]
		if lastDifference > 0:
			sum = sum + lastDifference
		else:
			sum = sum - lastDifference
	else:
		return 0
	return sum


def maxSum(arr, n):
	arr.sort()
	l = [0] * n
	m = 0
	p = -1
	for i in range(0, n, 2):
		l[i] = arr[m]
		m = m + 1
	for j in range(1, n, 2):
		l[j] = arr[p]
		p = p - 1
	s = abs(l[0] - l[-1])
	for k in range(1, n):
		s = s + abs(l[k - 1] - l[k])
	return s


def max_sum_absolute_diff(arr: [], n):
	sorted_arr = sorted(arr)
	reverse_sorted_arr = sorted(arr, reverse=True)
	i = 0
	j = 0
	while i < n:
		arr[i] = sorted_arr[j]
		if i + 1 < n:
			arr[i + 1] = reverse_sorted_arr[j]
		j = j + 1
		i = i + 2
	result = 0
	for i in range(0, n):
		if i == n - 1:
			j = 0
		else:
			j = i + 1
		diff = arr[i] - arr[j]
		result = result + abs(diff)
	return result

def maxSum(arr, n):
	return max_sum_absolute_diff(arr, n)


import collections

def maxSum(arr, n):
	arr.sort()
	dq = collections.deque([])
	i = 0
	j = n - 1
	cnt = 0
	while i < j:
		if cnt % 2 == 0:
			dq.append(arr[i])
			dq.appendleft(arr[j])
		else:
			dq.append(arr[j])
			dq.appendleft(arr[i])
		cnt += 1
		i += 1
		j -= 1
	if i == j:
		dq.append(arr[i])
	l = list(dq)
	ans = 0
	for i in range(n - 1):
		ans += abs(l[i] - l[i + 1])
	ans += abs(l[n - 1] - l[0])
	return ans


def maxSum(arr, n):
	arr.sort()
	start = 0
	end = n - 1
	potentialMax = 0
	while start < end:
		potentialMax += abs(arr[start] - arr[end]) + abs(arr[start + 1] - arr[end])
		start += 1
		end -= 1
	return potentialMax + abs(arr[0] - arr[start])


def maxSum(arr, n):
	arr.sort()
	l1 = []
	if n % 2 == 0:
		for i in range(n // 2):
			l1.append(arr[i])
			l1.append(arr[-i - 1])
	else:
		for i in range(n // 2):
			l1.append(arr[i])
			l1.append(arr[-i - 1])
		l1.append(arr[n // 2])
	l = []
	for i in range(len(l1) - 1):
		l.append(abs(l1[i] - l1[i + 1]))
	l.append(abs(l1[-1] - l1[0]))
	return sum(l)


def maxSum(arr, n):
	a = []
	arr.sort()
	if n % 2 == 0:
		for i in range(0, n // 2):
			a.append(arr[i])
			a.append(arr[n - (i + 1)])
	else:
		for i in range(0, n // 2):
			a.append(arr[i])
			a.append(arr[n - (i + 1)])
		a.append(arr[n // 2])
	sum1 = 0
	for i in range(0, n - 1):
		diff = a[i] - a[i + 1]
		if diff < 0:
			diff *= -1
			sum1 += diff
		else:
			sum1 += diff
	diff = a[n - 1] - a[0]
	if diff < 0:
		diff *= -1
		sum1 += diff
	else:
		sum1 += diff
	return sum1


def maxSum(a, n):
	a.sort()
	i = 0
	j = n - 1
	max_sum = 0
	while i < j:
		max_sum += abs(a[i] - a[j])
		max_sum += abs(a[i + 1] - a[j])
		i += 1
		j -= 1
	max_sum += abs(a[0] - a[i])
	return max_sum


def maxSum(arr, n):
	arr.sort()
	new_arr = []
	(left, right) = (0, len(arr) - 1)
	i = 0
	while i < len(arr):
		if i % 2 == 0:
			new_arr.append(arr[left])
			i += 1
			left += 1
			continue
		else:
			new_arr.append(arr[right])
			right -= 1
			i += 1
	sums = 0
	new_arr = new_arr + [new_arr[0]]
	for i in range(len(new_arr) - 1):
		sums += abs(new_arr[i] - new_arr[i + 1])
	return sums


def maxSum(arr, n):
	mid = n // 2
	arr.sort()
	arr1 = arr[:mid]
	arr2 = arr[mid:][::-1]
	ans = 0
	arr3 = []
	for i in range(min(len(arr1), len(arr2))):
		arr3.append(arr1[i])
		arr3.append(arr2[i])
	if n % 2 != 0:
		arr3.append(arr2[-1])
	prev = arr3[0]
	for i in range(1, n):
		ans += abs(prev - arr3[i])
		prev = arr3[i]
	ans += abs(arr3[0] - arr3[-1])
	return ans


def maxSum(arr, n):
	arr.sort()
	return 2 * (sum(arr[(n + 1) // 2:]) - sum(arr[:n // 2]))


def maxSum(arr, n):
	arr.sort()
	temp = []
	start = 0
	end = n - 1
	while start <= end:
		temp.append(arr[start])
		temp.append(arr[end])
		start += 1
		end -= 1
	ans = 0
	for i in range(1, n):
		ans += abs(temp[i] - temp[i - 1])
	ans += abs(temp[-1] - temp[0])
	return ans


def maxSum(arr, n):
	arr.sort()
	l = []
	if n % 2 == 0:
		k = n // 2
	else:
		k = n // 2 + 1
	for i in range(k):
		l.append(arr[i])
		l.append(arr[-(i + 1)])
	s = 0
	for i in range(1, n):
		s = s + abs(l[i] - l[i - 1])
	s = s + abs(l[0] - l[-1])
	return s


def maxSum(arr, n):
	arr.sort()
	rev = []
	for i in range(n - 1, -1, -1):
		rev.append(arr[i])
	sum = 0
	for i in range(n):
		sum += abs(rev[i] - arr[i])
	return sum


def maxSum(arr, n):
	arr.sort()
	(l, r) = (0, n - 1)
	left = True
	t = 0
	while l < r:
		diff = abs(arr[l] - arr[r])
		t += diff
		if left:
			l += 1
			left = False
		else:
			r -= 1
			left = True
	if n % 2 == 0:
		t += abs(arr[0] - arr[r])
	else:
		t += abs(arr[0] - arr[l])
	return t


def maxSum(arr, n):
	sm = 0
	arr.sort()
	i = 0
	j = len(arr) - 1
	l = []
	while i < j:
		l.append(arr[j])
		l.append(arr[i])
		i = i + 1
		j = j - 1
	for i in range(1, len(l)):
		sm = sm + abs(l[i] - l[i - 1])
	sm = sm + abs(l[0] - l[-1])
	return sm


def maxSum(s, n):
	s.sort()
	new = []
	while s:
		new.append(s.pop(0))
		if s:
			new.append(s.pop())
	summ = new[-1] - new[0]
	for i in range(len(new) - 1):
		summ += abs(new[i + 1] - new[i])
	return summ


def maxSum(arr, n):
	arr.sort()
	(i, j) = (0, n - 1)
	while i < j:
		if i % 2 != 0:
			(arr[i], arr[j]) = (arr[j], arr[i])
		i += 1
		j -= 1
	s = 0
	for i in range(n):
		if i == n - 1:
			s += abs(arr[i] - arr[0])
		else:
			s += abs(arr[i] - arr[i + 1])
	return s


def maxSum(arr, n):
	arr.sort()
	sum = 0
	for i in range(0, int(n / 2)):
		sum -= 2 * arr[i]
		sum += 2 * arr[n - i - 1]
	return sum
	i = 0
	j = n - 1
	while i < j:
		sum += abs(arr[i] - arr[j])
		sum += abs(arr[i + 1] - arr[j])
	sum += abs(arr[0] - arr[i])
	return sum


def maxSum(arr, n):
	arr.sort()
	sum_ = 0
	for index in range(n // 2):
		sum_ += abs(arr[index] - arr[-index - 1])
	return sum_ * 2