Given an unsorted array arr[ ] of size n, you need to find the maximum difference of absolute values of elements and indexes, i.e., for i <= j, calculate maximum of | arr[ i ] - arr[ j ] | + | i - j |. 
Example 1:
Input : 
n = 3
arr[ ] = {1, 3, -1}
Output: 5
Explanation:
Maximum difference comes from indexes 
1, 2 i.e | 3 - (-1) | + | 1 - 2 | = 5
Example 2:
Input : 
n = 4
arr[ ] = {5, 9, 2, 6} 
Output:  8
Explanation: 
Maximum difference comes from indexes 
1, 2 i.e | 9 - 2 | + | 1 - 2 | = 8
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maxDistance() that takes an array (arr), sizeOfArray (n), and return the maximum difference as given in the question.  The driver code takes care of the printing.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
 
Constraints:
1 <= n <= 5*(10^5)
-10^6 <= arr[ i ] <= 10^6

Difficulty: MEDIUM
Tags: Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).

Starter code:
class Solution:

    def maxDistance (self, arr, n) : 

        #Complete the function



Solutions:
class Solution:

	def maxDistance(self, a, n):
		for i in range(n):
			a[i] += i
		m1 = max(a)
		m2 = min(a)
		for i in range(n):
			a[i] -= 2 * i
		m3 = max(a)
		m4 = min(a)
		return max(m1 - m2, m3 - m4)


class Solution:

	def maxDistance(self, arr, n):
		max1 = float('-inf')
		min1 = float('inf')
		max2 = float('-inf')
		min2 = float('inf')
		for i in range(n):
			max1 = max(max1, arr[i] + i)
			min1 = min(min1, arr[i] + i)
			max2 = max(max2, arr[i] - i)
			min2 = min(min2, arr[i] - i)
		return max(max2 - min2, max1 - min1)


class Solution:

	def maxDistance(self, array, n):
		max1 = -2147483648
		min1 = +2147483647
		max2 = -2147483648
		min2 = +2147483647
		for i in range(len(array)):
			max1 = max(max1, array[i] + i)
			min1 = min(min1, array[i] + i)
			max2 = max(max2, array[i] - i)
			min2 = min(min2, array[i] - i)
		return max(max1 - min1, max2 - min2)


class Solution:

	def maxDistance(self, arr, n):
		cmin = cmax = arr[0]
		ans = 0
		for i in arr[1:]:
			cmin = min(cmin - 1, i)
			cmax = max(cmax + 1, i)
			ans = max(ans, i - cmin, cmax - i)
		return ans


import sys

class Solution:

	def maxDistance(self, arr, n):
		mini1 = sys.maxsize
		mini2 = sys.maxsize
		maxi1 = -sys.maxsize - 1
		maxi2 = -sys.maxsize - 1
		if n == 1:
			return 0
		for i in range(n):
			maxi1 = max(maxi1, arr[i] + i)
			mini1 = min(mini1, arr[i] + i)
			maxi2 = max(maxi2, arr[i] - i)
			mini2 = min(mini2, arr[i] - i)
		ans = max(abs(maxi1 - mini1), abs(maxi2 - mini2))
		return ans


class Solution:

	def maxDistance(self, arr, n):
		ans = 0
		maxx = minn = arr[0]
		for i in range(n):
			newMaxx = arr[i] - i
			newMinn = arr[i] + i
			ans = max(ans, maxx - newMaxx, newMinn - minn)
			maxx = max(maxx, newMaxx)
			minn = min(minn, newMinn)
		return ans


class Solution:

	def maxDistance(self, arr, n):
		r0 = arr[0]
		rn = arr[n - 1]
		v0p = v0m = vnp = vnm = 0
		i0p = i0m = 0
		inp = inm = n - 1
		for i in range(n):
			if arr[i] - r0 - i > v0p:
				v0p = arr[i] - r0 - i
				i0p = i
			if arr[i] - r0 + i < v0m:
				v0m = arr[i] - r0 + i
				i0m = i
			if arr[i] - rn - (n - 1 - i) > vnp:
				vnp = arr[i] - rn - (n - 1 - i)
				inp = i
			if arr[i] - rn + (n - 1 - i) < vnm:
				vnm = arr[i] - rn + (n - 1 - i)
				inm = i
		x1 = abs(arr[inp] - arr[i0m]) + abs(inp - i0m)
		x2 = abs(arr[inm] - arr[i0p]) + abs(inm - i0p)
		return max(x1, x2)


class Solution:

	def maxDistance(self, arr, n):
		(max1, min1, max2, min2) = (arr[0], arr[0], arr[0], arr[0])
		for i in range(1, n):
			max1 = max(max1, arr[i] - i)
			min1 = min(min1, arr[i] - i)
			max2 = max(max2, arr[i] + i)
			min2 = min(min2, arr[i] + i)
		return max(max1 - min1, max2 - min2)


class Solution:

	def maxDistance(self, arr, n):
		max1 = -100000
		max2 = -10000
		min1 = 10000
		min2 = 10000
		for i in range(n):
			max1 = max(max1, arr[i] + i)
			min1 = min(min1, arr[i] + i)
			max2 = max(max2, arr[i] - i)
			min2 = min(min2, arr[i] - i)
		res = max1 - min1
		ress = max2 - min2
		return max(res, ress)


class Solution:

	def maxDistance(self, arr, n):
		A1 = []
		A2 = []
		for i in range(n):
			A1.append(arr[i] - i)
			A2.append(arr[i] + i)
		return max(max(A1) - min(A1), max(A2) - min(A2))


class Solution:

	def maxDistance(self, a, n):
		ans = -int(1e+56)
		mx = -int(1e+56)
		mi = int(1e+56)
		for i in range(n):
			mx = max(mx, a[i] - i)
			mi = min(mi, a[i] + i)
			ans = max(ans, a[i] + i - mi, mx - (a[i] - i))
		return ans


import sys

class Solution:

	def maxDistance(self, arr, n):
		mx1 = -sys.maxsize - 1
		mn1 = sys.maxsize
		mx2 = -sys.maxsize - 1
		mn2 = sys.maxsize
		for i in range(n):
			mx1 = max(mx1, arr[i] + i)
			mn1 = min(mn1, arr[i] + i)
			mx2 = max(mx2, -arr[i] + i)
			mn2 = min(mn2, -arr[i] + i)
		return max(mx1 - mn1, mx2 - mn2)


class Solution:

	def maxDistance(self, arr, n):
		import math
		import sys as sys
		if n == 1:
			maxi = 0
		elif n > 1:
			minplus = sys.maxsize
			maxmoins = -sys.maxsize
			maxi = -sys.maxsize
			for i in range(0, n):
				minplus = min(minplus, arr[i] + i)
				maxmoins = max(maxmoins, arr[i] - i)
				maximum = max(arr[i] + i - minplus, maxmoins - (arr[i] - i))
				maxi = max(maxi, maximum)
		return maxi


import math

class Solution:

	def maxDistance(self, arr, n):
		ma1 = ma2 = -math.inf
		mi1 = mi2 = math.inf
		for i in range(n):
			ma1 = max(ma1, arr[i] + i)
			mi1 = min(mi1, arr[i] + i)
			ma2 = max(ma2, arr[i] - i)
			mi2 = min(mi2, arr[i] - i)
		return max(abs(ma1 - mi1), abs(ma2 - mi2))


class Solution:

	def maxDistance(self, arr, n):
		n = len(arr)
		(maxi1, maxi2) = (-float('inf'), -float('inf'))
		for i in range(n):
			f_i_1 = arr[i] - i
			f_i_2 = -arr[i] - i
			maxi1 = max(maxi1, f_i_1)
			maxi2 = max(maxi2, f_i_2)
		(maxj1, maxj2) = (-float('inf'), -float('inf'))
		for j in range(n):
			f_j_1 = -arr[j] + j
			f_j_2 = arr[j] + j
			maxj1 = max(maxj1, f_j_1)
			maxj2 = max(maxj2, f_j_2)
		ans1 = maxi1 + maxj1
		ans2 = maxi2 + maxj2
		ans = max(ans1, ans2)
		return ans


class Solution:

	def maxDistance(self, arr, n):
		largest1 = -1000000000.0
		smallest1 = 1000000000.0
		largest2 = -1000000000.0
		smallest2 = 1000000000.0
		for i in range(len(arr)):
			largest1 = max(largest1, arr[i] - i)
			smallest1 = min(smallest1, arr[i] - i)
			largest2 = max(largest2, arr[i] + i)
			smallest2 = min(smallest2, arr[i] + i)
		return max(largest1 - smallest1, largest2 - smallest2)


class Solution:

	def maxDistance(self, arr, n):
		a = [x - i for (i, x) in enumerate(arr)]
		b = [x + i for (i, x) in enumerate(arr)]
		return max(max(a) - min(a), max(b) - min(b))


class Solution:

	def maxDistance(self, arr, n):
		r = float('-inf')
		maxi = float('-inf')
		mini = float('+inf')
		for i in range(len(arr)):
			maxi = max(maxi, arr[i] - i)
			mini = min(mini, arr[i] + i)
			v1 = arr[i] + i - mini
			v2 = maxi - arr[i] + i
			r = max(r, v1, v2)
		return r


class Solution:

	def maxDistance(self, A, num):
		case1Max = caseMax = float('-inf')
		case2Min = case4Min = float('inf')
		for (i, num) in enumerate(A):
			case1Max = max(case1Max, num + i)
			case2Min = min(case2Min, num + i)
			caseMax = max(caseMax, num - i)
			case4Min = min(case4Min, num - i)
		return max(case1Max - case2Min, caseMax - case4Min)


class Solution:

	def maxDistance(self, arr, n):
		maxi1 = -pow(2, 32) + 1
		mini1 = pow(2, 32) - 1
		for i in range(n):
			cur = arr[i] - i
			if maxi1 < cur:
				maxi1 = cur
			if mini1 > cur:
				mini1 = cur
		ans1 = maxi1 - mini1
		maxi2 = -pow(2, 32) + 1
		mini2 = pow(2, 32) - 1
		for i in range(n):
			cur = arr[i] + i
			if maxi2 < cur:
				maxi2 = cur
			if mini2 > cur:
				mini2 = cur
		return max(ans1, maxi2 - mini2)


class Solution:

	def maxDistance(self, arr, n):
		mx1 = float('-inf')
		mn1 = float('inf')
		mx2 = float('-inf')
		mn2 = float('inf')
		for i in range(n):
			mx1 = max(mx1, arr[i] - i)
			mn1 = min(mn1, arr[i] - i)
			mx2 = max(mx2, arr[i] + i)
			mn2 = min(mn2, arr[i] + i)
		return max(abs(mx1 - mn1), abs(mx2 - mn2))


class Solution:

	def maxDistance(self, arr, n):
		mx1 = mx2 = float('-inf')
		mn1 = mn2 = float('inf')
		for (i, v) in enumerate(arr):
			mx1 = max(mx1, v - i)
			mx2 = max(mx2, v + i)
			mn1 = min(mn1, v - i)
			mn2 = min(mn2, v + i)
		return max(mx1 - mn1, mx2 - mn2)


import sys

class Solution:

	def maxDistance(self, arr, n):
		min1 = sys.maxsize
		min2 = sys.maxsize
		max1 = -sys.maxsize - 1
		max2 = -sys.maxsize - 1
		if n == 1:
			return 0
		for i in range(n):
			max1 = max(max1, arr[i] + i)
			min1 = min(min1, arr[i] + i)
			max2 = max(max2, arr[i] - i)
			min2 = min(min2, arr[i] - i)
		ans = max(abs(max1 - min1), abs(max2 - min2))
		return ans


class Solution:

	def maxDistance(self, arr, n):
		maxi = float('-inf')
		mini = float('inf')
		ans = float('-inf')
		for i in range(n):
			maxi = max(maxi, arr[i] - i)
			mini = min(mini, arr[i] + i)
			val1 = maxi + (i - arr[i])
			val2 = arr[i] + i - mini
			ans = max(ans, val1, val2)
		return ans


class Solution:

	def maxDistance(self, arr, n):
		max_diff = 0
		min_diff = 0
		start_i = 0
		for end_i in range(len(arr)):
			max_diff = max(max_diff, arr[end_i] - arr[start_i] + end_i - start_i)
			if arr[end_i] - arr[start_i] + end_i - start_i <= 0:
				start_i = end_i
		start_i
		for end_i in range(len(arr)):
			min_diff = min(min_diff, arr[end_i] - arr[start_i] - end_i + start_i)
			if arr[end_i] - arr[start_i] - end_i + start_i >= 0:
				start_i = end_i
		return max(max_diff, -min_diff)


import math

class Solution:

	def maxDistance(self, arr, n):
		l = len(arr)
		if l > 1:
			ans = -math.inf
			mini = maxi = 0
			for j in range(1, l):
				minv = arr[mini]
				maxv = arr[maxi]
				curv = arr[j]
				ans = max(ans, maxv - curv + j - maxi, curv - minv + j - mini)
				if curv - j > maxv - maxi:
					maxi = j
				if curv + j < minv + mini:
					mini = j
			return ans
		else:
			return 0


class Solution:

	def maxDistance(self, arr, n):
		mx1 = -1000000000.0
		mx2 = -1000000000.0
		mn1 = 1000000000.0
		mn2 = 1000000000.0
		for i in range(n):
			mx1 = max(mx1, arr[i] - i)
			mn1 = min(mn1, arr[i] - i)
			mx2 = max(mx2, arr[i] + i)
			mn2 = min(mn2, arr[i] + i)
		return max(mx1 - mn1, mx2 - mn2)


class Solution:

	def maxDistance(self, arr, n):
		l = []
		m = []
		for i in range(n):
			l.append(arr[i] + i)
			m.append(arr[i] - i)
		k = max(l) - min(l)
		e = max(m) - min(m)
		return max(k, e)


class Solution:

	def maxDistance(self, arr, n):
		ans = 0
		for index1 in range(n):
			for index2 in range(index1 + 1, n):
				ans = max(ans, abs(arr[index1] - arr[index2]) + abs(index1 - index2))
		return ans

	def maxDistance(self, arr, n):
		max1 = -32767
		max2 = -32767
		min1 = 32767
		min2 = 32767
		if n == 1:
			return 0
		for index in range(n):
			max1 = max(max1, arr[index] + index)
			min1 = min(min1, arr[index] + index)
			max2 = max(max2, arr[index] - index)
			min2 = min(min2, arr[index] - index)
		ans = max(max1 - min1, max2 - min2)
		return ans


class Solution:

	def maxDistance(self, arr, n):
		p = []
		s = []
		for i in range(n):
			n1 = arr[i] - i
			p.append(n1)
			n3 = arr[i] + i
			s.append(n3)
		p.sort()
		s.sort()
		x1 = p[len(p) - 1] - p[0]
		x2 = s[len(s) - 1] - s[0]
		ans1 = max(x1, x2)
		return ans1


class Solution:

	def maxDistance(self, arr, n):
		p = []
		s = []
		for i in range(n):
			k = arr[i] - i
			d = arr[i] + i
			s.append(k)
			p.append(d)
		p.sort()
		s.sort()
		x1 = p[len(p) - 1] - p[0]
		x2 = s[len(s) - 1] - s[0]
		ans = max(x1, x2)
		return ans


class Solution:

	def maxDistance(self, arr, n):
		while len(arr) > 1:
			max1 = -2147483648
			max2 = -2147483648
			min1 = arr[0] + 0
			min2 = arr[0] - 0
			sum = 0
			diff = 0
			for i in range(n):
				sum = arr[i] + i
				if sum > max1:
					max1 = sum
				if sum < min1:
					min1 = sum
				diff = arr[i] - i
				if diff > max2:
					max2 = diff
				if diff < min2:
					min2 = diff
			return max(max1 - min1, max2 - min2)
		return 0


import sys

class Solution:

	def maxDistance(self, arr, n):
		max1 = -sys.maxsize
		min1 = sys.maxsize
		max2 = -sys.maxsize
		min2 = sys.maxsize
		for i in range(n):
			max1 = max(max1, arr[i] - i)
			min1 = min(min1, arr[i] - i)
			max2 = max(max2, arr[i] + i)
			min2 = min(min2, arr[i] + i)
		ans = max(max1 - min1, max2 - min2)
		return ans


class Solution:

	def maxDistance(self, arr, n):
		max_1 = float('-inf')
		min_1 = float('inf')
		max_2 = float('-inf')
		min_2 = float('inf')
		for (idx, val) in enumerate(arr):
			max_1 = max(max_1, val + idx)
			min_1 = min(min_1, val + idx)
			max_2 = max(max_2, val - idx)
			min_2 = min(min_2, val - idx)
		return max(max_1 - min_1, max_2 - min_2)


class Solution:

	def maxDistance(self, a, n):
		ans = 0
		m1 = a[0] + 0
		m2 = -a[0] + 0
		for i in range(n):
			m1 = min(m1, a[i] + i)
			m2 = min(m2, -a[i] + i)
			ans = max(ans, a[i] + i - m1)
			ans = max(ans, -a[i] + i - m2)
		return ans


class Solution:

	def maxDistance(self, arr, n):
		ans = -10000000
		mx = -10000000
		mn = 10000000
		for i in range(n):
			mx = max(mx, arr[i] - i)
			mn = min(mn, arr[i] + i)
			v1 = arr[i] + i - mn
			v2 = mx - (arr[i] - i)
			ans = max(ans, max(v1, v2))
		return ans


class Solution:

	def maxDistance(self, a, n):
		max1 = -1000000000.0
		max2 = -1000000000.0
		min1 = 1000000000.0
		min2 = 1000000000.0
		for j in range(n):
			max2 = max(max2, a[j] - j)
			max1 = max(max1, a[j] + j)
			min2 = min(min2, a[j] - j)
			min1 = min(min1, a[j] + j)
		ans = max(max1 - min1, max2 - min2)
		return ans