Given an array(0-based indexing), you have to find the max sum of i*A[i] where A[i] is the element at index i in the array. The only operation allowed is to rotate(clock-wise or counter clock-wise) the array any number of times.
Example 1:
Input:
N = 4
A[] = {8,3,1,2}
Output: 29
Explanation: Above the configuration
possible by rotating elements are
3 1 2 8 here sum is 3*0+1*1+2*2+8*3 = 29
1 2 8 3 here sum is 1*0+2*1+8*2+3*3 = 27
2 8 3 1 here sum is 2*0+8*1+3*2+1*3 = 17
8 3 1 2 here sum is 8*0+3*1+1*2+2*3 = 11
Here the max sum is 29 
Your Task:
Your task is to complete the function max_sum which takes two arguments which is the array A [ ] and its size and returns an integer value denoting the required max sum.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1<=N<=10^{4}
1<=A[]<1000

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

def max_sum(a,n):
    #code here

Solutions:
def max_sum(a, n):
	total_sum = 0
	product_sum = 0
	if n == 1:
		return 0
	for i in range(n):
		total_sum += a[i]
		product_sum += a[i] * i
	max_product = product_sum
	for i in range(n - 1, -1, -1):
		product_sum = product_sum + total_sum - a[i] * n
		max_product = max(max_product, product_sum)
	return max_product


def max_sum(a, n):
	m = 0
	s = 0
	for i in range(0, n):
		s = s + a[i]
		m = m + i * a[i]
	an = m
	for i in range(0, n):
		m = m + s - a[n - 1 - i] * n
		an = max(m, an)
	return an


def max_sum(a, n):
	sum1 = 0
	csum1 = 0
	for i in range(n):
		sum1 += a[i]
		csum1 += i * a[i]
	M = csum1
	for j in range(1, n):
		csum1 += sum1 - n * a[n - j]
		if csum1 > M:
			M = csum1
	return M


def max_sum(a, n):
	arrsum = 0
	for i in arr:
		arrsum += i
	mulsum = 0
	for i in range(n):
		mulsum += i * arr[i]
	ans = mulsum
	for i in range(1, n):
		nsum = mulsum - (arrsum - arr[i - 1]) + arr[i - 1] * (n - 1)
		mulsum = nsum
		ans = max(ans, mulsum)
	return ans


def max_sum(a, n):
	res = 2 * a
	l = 0
	r = 0
	cur = 0
	cr = 0
	ans = 0
	while r < n:
		cr += res[r]
		cur += r * res[r]
		r += 1
	while r < 2 * n:
		cr -= res[l]
		cur -= cr
		cur += res[r] * (n - 1)
		ans = max(ans, cur)
		cr += res[r]
		r += 1
		l += 1
	return ans


def max_sum(arr, n):
	(total, prev_val) = (0, 0)
	for i in range(n):
		total += arr[i]
		prev_val += i * arr[i]
	res = prev_val
	for i in range(1, n):
		curr_val = prev_val - (total - arr[i - 1]) + (n - 1) * arr[i - 1]
		res = max(curr_val, res)
		prev_val = curr_val
	return res


def max_sum(array, n):
	(addition, temp) = (0, 0)
	for i in range(n):
		addition += array[i]
		temp += array[i] * i
	maxx = temp
	for i in range(n - 1):
		value = temp + addition - n * array[n - i - 1]
		if value > maxx:
			maxx = value
		temp = value
	return maxx


def max_sum(a, n):
	cum_sum = 0
	for i in range(0, n):
		cum_sum = cum_sum + a[i]
	initial_value = 0
	mx = 0
	for i in range(0, n):
		initial_value += i * a[i]
		mx = initial_value
	for i in range(1, n):
		temp = initial_value - (cum_sum - a[i - 1]) + a[i - 1] * (n - 1)
		initial_value = temp
		if temp > mx:
			mx = temp
	return mx


def max_sum(a, n):
	cum_sum = 0
	for i in range(0, n):
		cum_sum += arr[i]
	curr_val = 0
	for i in range(0, n):
		curr_val += i * arr[i]
	res = curr_val
	for i in range(1, n):
		next_val = curr_val - (cum_sum - arr[i - 1]) + arr[i - 1] * (n - 1)
		curr_val = next_val
		res = max(res, next_val)
	return res


def max_sum(a, n):
	(ans, k) = (0, sum(arr))
	for i in range(n):
		ans += i * arr[i]
	temp = ans
	for i in range(n):
		temp = temp + k - n * arr[n - i - 1]
		ans = max(ans, temp)
	return ans


def max_sum(a, n):
	rcb = 0
	csk = 0
	for i in range(n):
		rcb += a[i]
		csk += i * a[i]
	mi = csk
	for i in range(n):
		csk = csk - (rcb - a[i]) + a[i] * (n - 1)
		mi = max(mi, csk)
	return mi


def max_sum(a, n):
	(i, max_sum) = (0, 0)
	cur = 0
	while i < n:
		max_sum += i * a[i]
		cur += a[i]
		i += 1
	i = 1
	r_sum = max_sum
	while i < n:
		r_sum += cur - n * a[n - i]
		max_sum = max(max_sum, r_sum)
		i += 1
	return max_sum


def max_sum(a, n):
	maxi = -10 ** 9
	c = 0
	s = 0
	for i in range(n):
		c = c + a[i] * i
		s = s + a[i]
	maxi = max(maxi, c)
	for i in range(n - 1):
		c = c - (s - a[i]) + a[i] * (n - 1)
		maxi = max(c, maxi)
	return maxi


def max_sum(a, n):
	su = 0
	prev = 0
	for i in range(n):
		su += a[i]
		prev += i * a[i]
	mi = prev
	for i in range(n):
		prev = prev - (su - a[i]) + a[i] * (n - 1)
		mi = max(mi, prev)
	return mi


def max_sum(a, n):
	su = sum(a)
	max_sum = 0
	sum1 = 0
	for i in range(n):
		sum1 += arr[i] * i
	for i in range(n):
		t1 = su - arr[i]
		t2 = arr[i] * (n - 1)
		new_sum = sum1 + t2 - t1
		max_sum = max(max_sum, new_sum)
		sum1 = new_sum
	return max_sum


def max_sum(a, n):
	p_s = 0
	s = 0
	for i in range(n):
		p_s = p_s + i * a[i]
		s = s + a[i]
	max_sum = p_s
	for i in range(n):
		p_s = p_s + s - n * a[n - i - 1]
		max_sum = max(max_sum, p_s)
	return max_sum


def max_sum(a, n):
	if n == 1:
		return 0
	else:
		first_sum = 0
		for i in range(0, n):
			first_sum = first_sum + a[i] * i
		ma = first_sum
		total_sum = sum(a)
		for i in range(1, n):
			final_sum = first_sum - total_sum + arr[i - 1] * n
			first_sum = final_sum
			ma = max(ma, final_sum)
	return ma


def max_sum(a, n):
	sumi = sum(a)
	rotationSum = 0
	for i in range(n):
		rotationSum += a[i] * i
	maxi = rotationSum
	for i in range(1, n):
		currentRotationSum = rotationSum + sumi - a[n - i] - (n - 1) * a[n - i]
		maxi = max(maxi, currentRotationSum)
		rotationSum = currentRotationSum
	return maxi


def max_sum(a, n):
	sum_ = sum(a)
	sumcurrent = 0
	for i in range(n):
		sumcurrent += a[i] * i
	max_ = sumcurrent
	for i in range(n - 1):
		sumcurrent = sumcurrent + sum_ - n * a[n - 1 - i]
		max_ = max(max_, sumcurrent)
	return max_


def max_sum(a, n):
	s = sum(a)
	cur_sum = 0
	for i in range(n):
		cur_sum += a[i] * i
	ans = cur_sum
	for i in range(1, n):
		nextsum = cur_sum - (s - a[i - 1]) + a[i - 1] * (n - 1)
		cur_sum = nextsum
		ans = max(ans, nextsum)
	return ans


def max_sum(a, n):
	new = [a[-1]]
	new.extend(a)
	if n == 1:
		return 0
	Sum = sum(a[:n - 1])
	SLIndex = n - 1
	last = a[-1]
	s_last = a[-2]
	Initial = 0
	for i in range(n):
		Initial += i * a[i]
	Max = Initial
	for i in range(n - 1):
		Initial -= last * (n - 1)
		Initial += Sum
		if Initial > Max:
			Max = Initial
		Sum += last
		Sum -= s_last
		last = s_last
		SLIndex -= 1
		s_last = new[SLIndex]
	return Max


def max_sum(a, n):
	ans = []
	sum = 0
	curSum = 0
	for i in range(n):
		sum += a[i]
	for i in range(n):
		curSum += i * a[i]
	max = curSum
	preSum = curSum
	for i in range(0, n):
		newSum = preSum + sum - n * a[n - i - 1]
		if max < newSum:
			max = newSum
		preSum = newSum
	return max


def max_sum(a, n):
	arr_sum = sum(a)
	arr_val = sum((i * a[i] for i in range(n)))
	max_val = arr_val
	for i in range(1, n):
		arr_val = arr_val + arr_sum - n * a[n - i]
		max_val = max(max_val, arr_val)
	return max_val


def max_sum(a, n):
	s = sum(a)
	ss = 0
	for i in range(n):
		ss += a[i] * i
	ans = 0
	pop = ss
	for i in range(n):
		pop = pop + (n * a[i] - s)
		if pop > ans:
			ans = pop
	return ans


def max_sum(a, n):
	fs = 0
	for i in range(n):
		fs += i * a[i]
	ss = sum(a)
	m = fs
	for i in range(1, n):
		fs -= ss - a[i - 1]
		fs += a[i - 1] * (n - 1)
		if fs > m:
			m = fs
	return m


def max_sum(a, n):
	sum1 = 0
	curr = 0
	for i in range(n):
		sum1 += a[i]
		curr += i * a[i]
	nex = curr
	res = 0
	for i in range(n):
		nex = curr - (sum1 - a[i]) + a[i] * (n - 1)
		curr = nex
		res = max(res, nex)
	return res


def max_sum(a, n):
	sum = 0
	maxsum = 0
	for i in range(n):
		sum += a[i]
		maxsum += a[i] * i
	maxx = maxsum
	for i in range(n):
		maxsum = maxsum - sum + a[i] * n
		if maxsum > maxx:
			maxx = maxsum
	return maxx


def max_sum(a, n):
	curr_sum = 0
	curr_val = 0
	ans = 0
	for i in range(n):
		curr_sum += a[i]
		curr_val += a[i] * i
	ans = curr_val
	for i in range(1, n):
		next_val = curr_val - (curr_sum - a[i - 1]) + a[i - 1] * (n - 1)
		curr_val = next_val
		ans = max(ans, next_val)
	return ans


def max_sum(arr, n):
	ans = 0
	total = 0
	for i in range(n):
		total += arr[i] * i
	ans = total
	Sum = sum(arr)
	for i in range(n - 1):
		total -= n * arr[n - i - 1] - Sum
		if total > ans:
			ans = total
	return ans


def max_sum(arr, n):
	s = 0
	for i in range(n):
		s += arr[i] * i
	total_sum = sum(arr)
	max_s = s
	for i in range(n):
		s = s + arr[i] * n
		s -= total_sum
		max_s = max(s, max_s)
	return max_s


def max_sum(a, n):
	NS = -sum(a)
	V = ans = sum([i * v for (i, v) in enumerate(a)])
	for i in range(1, n):
		V += NS + n * a[i - 1]
		ans = max(ans, V)
	return ans


def max_sum(a, n):
	(s1, s2) = (0, 0)
	for i in range(n):
		s1 += a[i]
		s2 += i * a[i]
	res = s2
	for i in range(1, n):
		s2 = s2 + s1 - n * a[n - i]
		res = max(res, s2)
	return res


def max_sum(arr, n):
	(arrSum, currSum) = (0, 0)
	for i in range(n):
		(arrSum, currSum) = (arrSum + arr[i], currSum + i * arr[i])
	maxSum = currSum
	for j in range(1, n):
		currSum += arrSum - n * arr[n - j]
		maxSum = max(maxSum, currSum)
	return maxSum


def max_sum(a, n):
	su = sum(a)
	curr_sum = 0
	for i in range(n):
		curr_sum = curr_sum + i * a[i]
	max_sum = curr_sum
	for i in range(n):
		curr_sum = curr_sum + (su - n * a[n - 1 - i])
		max_sum = max(max_sum, curr_sum)
	return max_sum


def max_sum(a, n):
	sum = 0
	rotational_sum = 0
	for i in range(n):
		sum += a[i]
		rotational_sum += a[i] * i
	ans = rotational_sum
	for i in range(1, n):
		rotational_sum = rotational_sum + sum - n * a[n - i]
		ans = max(ans, rotational_sum)
	return ans


def max_sum(A, N):
	NS = -sum(A)
	V = ans = sum([i * v for (i, v) in enumerate(A)])
	for i in range(1, N):
		V += NS + N * A[i - 1]
		ans = max(ans, V)
	return ans


def max_sum(a, n):
	sum1 = 0
	prev = 0
	for i in range(len(a)):
		sum1 += a[i]
		prev += i * a[i]
	ans = prev
	for i in range(len(a)):
		prev = prev - (sum1 - a[i]) + a[i] * (len(a) - 1)
		ans = max(ans, prev)
	return ans


def max_sum(a, n):
	cnt = prev = 0
	for j in range(n):
		cnt += a[j]
		prev += j * a[j]
	ans = prev
	for i in range(n):
		prev = prev - (cnt - a[i]) + a[i] * (n - 1)
		ans = max(ans, prev)
	return ans


def max_sum(a, n):
	sum = 0
	last = 0
	for i in range(n):
		sum += a[i]
		last += i * a[i]
	result = last
	for i in range(n):
		last = last - (sum - a[i]) + a[i] * (n - 1)
		result = max(result, last)
	return result


def max_sum(arr, n):
	arr_sum = sum(arr)
	rotation_sum = sum((i * arr[i] for i in range(n)))
	max_sum = rotation_sum
	for i in range(1, n):
		rotation_sum = rotation_sum + arr_sum - n * arr[n - i]
		max_sum = max(max_sum, rotation_sum)
	return max_sum

def left_rotate_array(arr, size, d):
	reverse(arr, 0, d - 1)
	reverse(arr, d, size - 1)
	reverse(arr, 0, size - 1)
	return arr

def reverse(arr, start, end):
	while start < end:
		(arr[start], arr[end]) = (arr[end], arr[start])
		start += 1
		end -= 1


def max_sum(a, n):
	max_sum = 0
	cur_sum = 0
	for i in range(n):
		cur_sum += i * a[i]
	max_sum = cur_sum
	arr_sum = sum(arr)
	for i in range(1, n):
		next_config_sum = cur_sum - arr_sum + arr[i - 1] * n
		max_sum = max(max_sum, next_config_sum)
		cur_sum = next_config_sum
	return max_sum


def max_sum(a, n):
	curmax = 0
	arrsum = 0
	for i in range(n):
		curmax += i * a[i]
		arrsum += a[i]
	maxvalue = curmax
	for j in range(n - 1):
		curmax = curmax - (arrsum - n * arr[j])
		if curmax > maxvalue:
			maxvalue = curmax
	return maxvalue


def max_sum(a, n):
	l = [int(i) for i in range(n)]
	s = [0 for _ in range(n)]
	for i in range(n):
		s[0] += a[i] * i
	p = sum(a)
	for i in range(n - 1):
		s[i + 1] = n * a[i] - p + s[i]
	return max(s)


def max_sum(a, n):
	tot = sum(a)
	maxans = 0
	for (i, ele) in enumerate(arr):
		maxans += i * ele
	ans = 0
	for ele in arr:
		maxans = maxans - tot + n * ele
		ans = max(ans, maxans)
	return ans


def max_sum(a, n):
	a = arr
	array_sum = sum(arr)
	cur_sum = sum((i * arr[i] for i in range(n)))
	max_sum = cur_sum
	for i in range(n):
		cur_sum += n * arr[i] - array_sum
		max_sum = max(max_sum, cur_sum)
	return max_sum


def max_sum(arr, n):
	sum = 0
	csum = 0
	for i in range(n):
		sum += arr[i]
		csum += i * arr[i]
	result = csum
	for j in range(1, n):
		csum += sum - n * arr[n - j]
		if csum > result:
			result = csum
	return result


def max_sum(a, n):
	(arrSum, S) = (0, 0)
	for i in range(n):
		arrSum += a[i] * i
		S += a[i]
	ans = arrSum
	for i in range(1, n, 1):
		arrSum = arrSum - S + a[i - 1] * n
		ans = max(ans, arrSum)
	return ans


def max_sum(a, n):
	prefix_sum = 0
	index_sum = 0
	for (index, num) in enumerate(a):
		prefix_sum += num
		index_sum += index * num
	max_rotation_sum = index_sum
	for i in range(1, n):
		index_sum = index_sum - prefix_sum + n * a[i - 1]
		max_rotation_sum = max(index_sum, max_rotation_sum)
	return max_rotation_sum


def max_sum(a, n):
	array_sum = sum(a)
	curr_val = sum([i * a[i] for i in range(0, n)])
	res = curr_val
	for i in range(0, n - 1):
		next_val = curr_val - array_sum + n * a[i]
		curr_val = next_val
		res = max(res, next_val)
	return res


def max_sum(a, n):
	sm = sum(a)
	prev_sum = sum(list(map(lambda x, i: x * i, a, range(len(a)))))
	mx = prev_sum
	for i in range(1, len(a)):
		sum_ith = sm + prev_sum - n * a[n - i]
		if sum_ith > mx:
			mx = sum_ith
		prev_sum = sum_ith
	return mx


def max_sum(a, n):
	sumi = 0
	res = 0
	for i in range(n):
		sumi += a[i]
		res += a[i] * i
	maxi = res
	for i in range(n):
		res = res - (sumi - a[i]) + a[i] * (n - 1)
		maxi = max(maxi, res)
	return maxi


def rotate(A, N):
	sm1 = 0
	sm2 = 0
	for i in range(N - 1):
		sm1 += abs(A[i] * i - A[i + 1] * (i + 1))
		(A[i], A[i + 1]) = (A[i + 1], A[i])
		sm2 += abs(A[i] * i - A[i + 1] * (i + 1))
	if sm1 > sm2:
		return 1
	else:
		return 0

def max_sum(a, n):
	sm = 0
	pr = 0
	for i in range(n):
		sm += a[i]
		pr += a[i] * i
	mx = pr
	for i in range(n):
		pr = pr - sm + a[i] + a[i] * (n - 1)
		mx = max(mx, pr)
	return mx
	return val


def max_sum(a, n):
	sum = 0
	curr_val = 0
	for i in range(n):
		sum += a[i]
		curr_val += i * a[i]
	max_val = curr_val
	for i in range(1, n):
		next_val = curr_val - (sum - a[i - 1]) + a[i - 1] * (n - 1)
		curr_val = next_val
		max_val = max(max_val, curr_val)
	return max_val


def max_sum(a, n):
	s1 = 0
	s = 0
	for i in range(n):
		s1 = s1 + a[i] * i
		s += a[i]
	ma = s1
	for i in range(n):
		s1 = s1 + s - n * a[n - i - 1]
		ma = max(ma, s1)
	return ma


def max_sum(a, n):
	sum = 0
	total = 0
	for i in range(n):
		sum += a[i]
		total += a[i] * i
	maxi = total
	for i in range(1, n):
		total = total - n * a[n - i] + sum
		maxi = max(maxi, total)
	return maxi


def max_sum(a, n):
	sum = 0
	prev = 0
	for i in range(0, n):
		sum = sum + arr[i]
		prev = prev + arr[i] * i
	mx = prev
	for i in range(0, n):
		prev = prev - (sum - arr[i]) + arr[i] * (n - 1)
		mx = max(prev, mx)
	return mx


def max_sum(a, n):
	s = sum(a)
	max_so_far = 0
	res = 0
	for i in range(n):
		max_so_far = max_so_far + arr[i] * i
	for i in range(n):
		temp = max_so_far - s + arr[i] + arr[i] * (n - 1)
		max_so_far = temp
		res = max(res, temp)
	return res


def max_sum(arr, n):
	arrSum = sum(arr)
	idxSum = sum((i * arr[i] for i in range(n)))
	ans = idxSum
	for i in range(1, n):
		idxSum = idxSum + arrSum - n * arr[n - i]
		ans = max(ans, idxSum)
	return ans


def max_sum(arr, n):
	arr_sum = sum(arr)
	rotation_sum = sum((i * arr[i] for i in range(n)))
	max_sum = rotation_sum
	for i in range(1, n):
		rotation_sum = rotation_sum + arr_sum - n * arr[n - i]
		max_sum = max(max_sum, rotation_sum)
	return max_sum


import numpy as np

def max_sum(a, n):
	sum1 = sum(a)
	sum2 = 0
	for i in range(n):
		sum2 += i * a[i]
	maximum = sum2
	for i in range(-1, -n, -1):
		sum3 = sum2 + (sum1 - a[i]) - a[i] * (n - 1)
		maximum = max(maximum, sum3)
		sum2 = sum3
	return maximum


def max_sum(a, n):
	sum_of_array = 0
	S0 = 0
	for i in range(n):
		sum_of_array += a[i]
		S0 += i * a[i]
	ans = S0
	for i in range(n - 1):
		next_cumsum = sum_of_array + S0 - n * a[n - i - 1]
		S0 = next_cumsum
		ans = max(ans, next_cumsum)
	return ans