Given an array arr[] of N positive integers. Find maximum value of |arr[i] – arr[j]| + |i – j|, (0 <= i, j <= N – 1)
 
Example 1:
Input:
N = 4 
arr[] = {1, 2, 3, 1}
Output:
4
Explanation:
Choosing i=0 and j=2, will result in
|1-3|+|0-2| = 4, which is the maximum
possible value.
Example 2:
Input:
N = 3 
A[] = {1, 1, 1}
Output:
2
Explanation:
Choosing i=0 and j=2, will result in
|1-1|+|0-2| = 2, which is the maximum
possible value.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxValue() which takes an Integer N and an array arr of size N as input and returns the maximum possoble value of |arr[i] – arr[j]| + |i – j|.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
0 <= arr[i] <= 10^{5}

Difficulty: MEDIUM
Tags: Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def maxValue(self, arr, N):

        # code here 

Solutions:
class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] + i)
			b.append(-arr[i] + i)
		mx = max(a)
		mn = min(a)
		mx1 = max(b)
		mn1 = min(b)
		return max(mx - mn, mx1 - mn1)


class Solution:

	def maxValue(self, arr, N):
		(a, b, c, d) = (0, 0, 100000, 100000)
		for i in range(0, N):
			a = max(a, arr[i] + i)
			b = max(b, arr[i] - i)
			c = min(c, arr[i] + i)
			d = min(d, arr[i] - i)
		return max(a - c, b - d)


import sys

class Solution:

	def maxValue(self, arr, N):
		max1 = 0
		max2 = 0
		min1 = sys.maxsize
		min2 = sys.maxsize
		mins = []
		for (i, item) in enumerate(arr):
			max1 = max(max1, i + item)
			max2 = max(max2, item - i)
			min1 = min(min1, i + item)
			min2 = min(min2, item - i)
		res = 0
		res = max(res, max1 - min1)
		res = max(res, max2 - min2)
		return res


class Solution:

	def maxValue(self, arr, N):
		max1 = -100000000.0
		min1 = 100000000.0
		max2 = -100000000.0
		min2 = 100000000.0
		for i in range(N):
			t1 = arr[i] + i
			t2 = arr[i] - i
			max1 = max(max1, t1)
			min1 = min(min1, t1)
			max2 = max(max2, t2)
			min2 = min(min2, t2)
		return max(max1 - min1, max2 - min2)


class Solution:

	def maxValue(self, arr, N):
		max1 = -2147483648
		min1 = 2147483647
		max2 = -2147483648
		min2 = 2147483647
		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(max1 - min1, max2 - min2)


class Solution:

	def maxValue(self, arr, N):
		l = []
		ans = -1
		for i in range(N):
			l.append(i + arr[i])
		ans = max(ans, max(l) - min(l))
		l = []
		for i in range(N):
			l.append(arr[i] - i)
		ans = max(ans, max(l) - min(l))
		return ans


class Solution:

	def maxValue(self, arr, N):
		(a, b) = ([], [])
		for i in range(N):
			a.append(arr[i] + i)
			b.append(-arr[i] + i)
		(mxa, mna) = (max(a), min(a))
		(mxb, mnb) = (max(b), min(b))
		return max(mxa - mna, mxb - mnb)


class Solution:

	def maxValue(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 maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] + i)
			b.append(-arr[i] + i)
		mx1 = max(a)
		mn1 = min(a)
		mx2 = max(b)
		mn2 = min(b)
		return max(mx1 - mn1, mx2 - mn2)


class Solution:

	def maxValue(self, a, n):
		max1 = a[0]
		min1 = a[0]
		max2 = a[0]
		min2 = a[0]
		for i in range(1, n):
			if a[i] + i > max1:
				max1 = a[i] + i
			if a[i] + i < min1:
				min1 = a[i] + i
			if a[i] - i > max2:
				max2 = a[i] - i
			if a[i] - i < min2:
				min2 = a[i] - i
		return max(max1 - min1, max2 - min2)


class Solution:

	def maxValue(self, arr, N):
		min1 = 100000
		min2 = 100000
		max1 = 0
		max2 = 0
		for i in range(N):
			min1 = min(min1, arr[i] + i)
			max1 = max(max1, arr[i] + i)
			min2 = min(min2, arr[i] - i)
			max2 = max(max2, arr[i] - i)
		return max(abs(min1 - max1), abs(min2 - max2))


class Solution:

	def maxValue(self, arr, N):
		import math
		a = c = -math.inf
		b = d = -a
		for i in range(len(arr)):
			(addition, diff) = (arr[i] + i, arr[i] - i)
			a = max(a, addition)
			b = min(b, addition)
			c = max(c, diff)
			d = min(d, diff)
		return max(a - b, c - d)


import sys

class Solution:

	def maxValue(self, arr, N):
		min1 = sys.maxsize
		min2 = sys.maxsize
		max1 = -sys.maxsize - 1
		max2 = -sys.maxsize - 1
		for (i, num) in enumerate(arr):
			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 maxValue(self, arr, N):
		max1 = -float('inf')
		min1 = float('inf')
		for i in range(N):
			temp = i + arr[i]
			max1 = max(max1, temp)
			min1 = min(min1, temp)
		ans1 = max1 - min1
		max2 = -float('inf')
		min2 = float('inf')
		for i in range(N):
			temp = i - arr[i]
			max2 = max(max2, temp)
			min2 = min(min2, temp)
		ans2 = max2 - min2
		return max(ans1, ans2)


class Solution:

	def maxValue(self, arr, N):
		mx1 = arr[0] - 0
		mx2 = arr[0] + 0
		mn1 = arr[0] - 0
		mn2 = arr[0] + 0
		for i in range(1, N):
			temp1 = arr[i] - i
			temp2 = arr[i] + i
			mx1 = max(mx1, temp1)
			mx2 = max(mx2, temp2)
			mn1 = min(mn1, temp1)
			mn2 = min(mn2, temp2)
		return max(mx1 - mn1, mx2 - mn2)


class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] + i)
			b.append(arr[i] - i)
		x = a[0]
		y = a[0]
		for i in range(N):
			if a[i] > x:
				x = a[i]
			if a[i] < y:
				y = a[i]
		ans1 = x - y
		x = b[0]
		y = b[0]
		for i in range(N):
			if b[i] > x:
				x = b[i]
			if b[i] < y:
				y = b[i]
		ans2 = x - y
		return max(ans1, ans2)


class Solution:

	def maxValue(self, arr, N):
		min1 = 999999999999999999
		min2 = 999999999999999999
		max1 = -99999999999999999
		max2 = -99999999999999999
		for i in range(N):
			max1 = max(arr[i] + i, max1)
			max2 = max(arr[i] - i, max2)
			min1 = min(arr[i] + i, min1)
			min2 = min(arr[i] - i, min2)
		return max(max1 - min1, max2 - min2)


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

class Solution:

	def maxValue(self, arr, N):
		return maxdiff(arr, N)


def maxdiff(arr, n):
	first = []
	second = []
	for i in range(n):
		first.append(arr[i] - i)
		second.append(arr[i] + i)
	ans1 = max(first) - min(first)
	ans2 = max(second) - min(second)
	return max(ans1, ans2)

class Solution:

	def maxValue(self, arr, N):
		return maxdiff(arr, N)


class Solution:

	def maxValue(self, arr, N):
		f = arr[0] + 0
		j = arr[0] - 0
		k = arr[0] + 0
		l = arr[0] - 0
		for i in range(N):
			f = max(f, arr[i] + i)
			j = min(j, arr[i] + i)
			k = max(k, arr[i] - i)
			l = min(l, arr[i] - i)
		a = abs(f - j)
		b = abs(k - l)
		return max(a, b)


class Solution:

	def maxValue(self, arr, N):
		l = []
		m = []
		(min1, min2, max1, max2) = (arr[0], arr[0], arr[0], arr[0])
		for i in range(1, N):
			if arr[i] + i > max1:
				max1 = arr[i] + i
			if arr[i] + i < min1:
				min1 = arr[i] + i
			if arr[i] - i < min2:
				min2 = arr[i] - i
			if arr[i] - i > max2:
				max2 = arr[i] - i
		ans = max(max1 - min1, max2 - min2)
		return ans


class Solution:

	def maxValue(self, arr, N):
		(tmp1, tmp2) = (0, 0)
		(max1, max2) = (-10 ** 6, -10 ** 6)
		(min1, min2) = (10 ** 6, 10 ** 6)
		for i in range(N):
			tmp1 = arr[i] + i
			tmp2 = arr[i] - i
			max1 = max(tmp1, max1)
			min1 = min(tmp1, min1)
			max2 = max(tmp2, max2)
			min2 = min(tmp2, min2)
		return max(max1 - min1, max2 - min2)


class Solution:

	def maxValue(self, a, n):
		maxai = a[0]
		minai = a[0]
		maxaii = a[0]
		minaii = a[0]
		for i in range(n):
			maxai = max(maxai, a[i] + i)
			minai = min(minai, a[i] + i)
			maxaii = max(maxaii, a[i] - i)
			minaii = min(minaii, a[i] - i)


class Solution:

	def maxValue(self, arr, N):
		case_1_min = 10 ** 6
		case_1_max = -10 ** 6
		case_1_val = 0
		case_2_min = 10 ** 6
		case_2_max = -10 ** 6
		case_2_val = 0
		for i in range(N):
			if arr[i] + i < case_1_min:
				case_1_min = arr[i] + i
			if arr[i] + i > case_1_max:
				case_1_max = arr[i] + i
			if arr[i] - i < case_2_min:
				case_2_min = arr[i] - i
			if arr[i] - i > case_2_max:
				case_2_max = arr[i] - i
		case_1_val = case_1_max - case_1_min
		case_2_val = case_2_max - case_2_min
		if case_1_val > case_2_val:
			return case_1_val
		return case_2_val


class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] + i)
			b.append(-arr[i] + i)
		mx = max(a)
		mn = min(a)
		mx1 = max(b)
		mn1 = min(b)
		return max(mx - mn, mx1 - mn1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxValue(arr, N))


class Solution:

	def maxValue(self, arr, N):
		mi1 = mi2 = 99999999
		ma1 = ma2 = -9999999
		for i in range(N):
			mi1 = min(mi1, i + arr[i])
			ma1 = max(ma1, i + arr[i])
			mi2 = min(mi2, i - arr[i])
			ma2 = max(ma2, i - arr[i])
		return max(ma1 - mi1, ma2 - mi2)


class Solution:

	def maxValue(self, arr, N):
		inf = float('inf')
		(min1, min2, max1, max2, ans) = (inf, inf, -inf, -inf, -inf)
		for (idx, i) in enumerate(arr):
			min1 = min(i - idx, min1)
			min2 = min(i + idx, min2)
			max1 = max(i - idx, max1)
			max2 = max(i + idx, max2)
			ans = max(ans, max1 - min1, max2 - min2)
		return ans


import sys

class Solution:

	def maxValue(self, arr, N):
		mx1 = -sys.maxsize - 1
		mx2 = -sys.maxsize - 1
		mn1 = sys.maxsize
		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)
		ans1 = mx1 - mn1
		ans2 = mx2 - mn2
		return max(ans1, ans2)


class Solution:

	def maxValue(self, arr, N):
		mx1 = mx2 = -999999
		mn1 = mn2 = 99999999
		for i in range(len(arr)):
			t1 = arr[i] + i
			t2 = -arr[i] + i
			mx1 = max(mx1, t1)
			mn1 = min(mn1, t1)
			mx2 = max(mx2, t2)
			mn2 = min(mn2, t2)
		return max(mx1 - mn1, mx2 - mn2)


class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] + i)
			b.append(arr[i] - i)
		(min_a, max_a) = (min(a), max(a))
		(min_b, max_b) = (min(b), max(b))
		ans1 = max_a - min_a
		ans2 = max_b - min_b
		return max(ans1, ans2)


class Solution:

	def maxValue(self, arr, n):

		def solve(arr, n):
			st = []
			ans = 0
			for i in range(n):
				if i == 0:
					st.append((arr[i], i))
				elif arr[i] >= st[-1][0]:
					ans = max(ans, arr[i] - st[-1][0] + (i - st[-1][1]))
				else:
					ans = max(ans, abs(arr[i] - st[-1][0]) + (i - st[-1][1]))
					if i - st[-1][1] < abs(arr[i] - st[-1][0]):
						st.pop()
						st.append((arr[i], i))
			return ans
		return max(solve(arr, n), solve(arr[::-1], n))


class Solution:

	def maxValue(self, arr, N):
		max1 = float('-inf')
		min1 = float('inf')
		max2 = float('-inf')
		min2 = float('inf')
		for i in range(len(arr)):
			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 maxValue(self, a, n):
		(max1, max2) = (-999999, -999999)
		(min1, min2) = (999999, 999999)
		for i in range(n):
			max1 = max(a[i] + i, max1)
			max2 = max(-a[i] + i, max2)
			min1 = min(a[i] + i, min1)
			min2 = min(-a[i] + i, min2)
		return max(max1 - min1, max2 - min2)


class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] - i)
			b.append(arr[i] + i)
		ans1 = max(a) - min(a)
		ans2 = max(b) - min(b)
		return max(ans1, ans2)


class Solution:

	def maxValue(self, arr, n):
		l = []
		p = []
		for i in range(n):
			l.append(arr[i] + i)
			p.append(-arr[i] + i)
		mxl = max(l)
		mnl = min(l)
		mxp = max(p)
		mnp = min(p)
		p = max(mxl - mnl, mxp - mnp)
		return p


class Solution:

	def maxValue(self, arr, N):
		sumArr = []
		diffArr = []
		for (i, ele) in enumerate(arr):
			sumArr.append(ele + i)
			diffArr.append(ele - i)
		maxSum = max(sumArr)
		minSum = min(sumArr)
		maxDiff = max(diffArr)
		minDiff = min(diffArr)
		eq1 = maxSum - minSum
		eq2 = maxDiff - minDiff
		return max(eq1, eq2)


class Solution:

	def maxValue(self, arr, N):
		a = []
		for i in range(0, N):
			a.append(-arr[i] + i)
			arr[i] = arr[i] + i
		mx1 = max(arr)
		min1 = min(arr)
		mx2 = max(a)
		min2 = min(a)
		return max(mx1 - min1, mx2 - min2)


class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] + i)
			b.append(arr[i] - i)
		maxa = max(a)
		mina = min(a)
		maxb = max(b)
		minb = min(b)
		return max(maxa - mina, maxb - minb)


class Solution:

	def maxValue(self, arr, n):
		ans1 = 0
		ans2 = 0
		max1 = min1 = arr[0]
		max2 = min2 = 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 maxValue(self, arr, n):
		a = []
		b = []
		for i in range(n):
			a.append(arr[i] + i)
			b.append(arr[i] - i)
		x = max(a)
		y = min(a)
		ans1 = x - y
		x = max(b)
		y = min(b)
		ans2 = x - y
		return max(ans1, ans2)


class Solution:

	def maxValue(self, arr, N):
		MaxDiff = arr[0]
		MinDiff = arr[0]
		res = 0
		for i in range(1, N):
			diff1 = arr[i] + i - MinDiff
			diff2 = i - arr[i] + MaxDiff
			res = max([res, diff1, diff2])
			MaxDiff = max(MaxDiff, arr[i] - i)
			MinDiff = min(MinDiff, arr[i] + i)
		return res


import sys

class Solution:

	def maxValue(self, arr, N):
		temp1 = 0
		temp2 = 0
		min1 = sys.maxsize
		min2 = sys.maxsize
		max1 = -sys.maxsize
		max2 = -sys.maxsize
		for i in range(N):
			temp1 = arr[i] + i
			temp2 = arr[i] - i
			max1 = max(max1, temp1)
			min1 = min(temp1, min1)
			max2 = max(max2, temp2)
			min2 = min(temp2, min2)
		return max(max2 - min2, max1 - min1)


import math
import numpy as np

class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for i in range(N):
			a.append(arr[i] + i)
			b.append(arr[i] - i)
		a1 = max(a)
		a2 = min(a)
		b1 = max(b)
		b2 = min(b)
		return max(a1 - a2, b1 - b2)


class Solution:

	def maxValue(self, arr, N):
		a = []
		b = []
		for (i, j) in enumerate(arr):
			a.append(j + i)
			b.append(i - j)
		amax = max(a)
		amin = min(a)
		bmax = max(b)
		bmin = min(b)
		k = amax - amin
		l = bmax - bmin
		return max(k, l)


class Solution:

	def maxValue(self, arr, N):
		maxAdd = arr[0]
		maxSub = arr[0]
		minAdd = arr[0]
		minSub = arr[0]
		for i in range(1, N):
			maxAdd = max(maxAdd, arr[i] + i)
			maxSub = max(maxSub, arr[i] - i)
			minAdd = min(minAdd, arr[i] + i)
			minSub = min(minSub, arr[i] - i)
		return max(maxAdd - minAdd, maxSub - minSub)


class Solution:

	def maxValue(self, arr, N):
		max1 = max2 = -99999999
		min1 = min2 = 999999999
		for i in range(len(arr)):
			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 maxValue(self, arr, N):
		mini = []
		maxi = []
		for i in range(N):
			mini.append(arr[i] - i)
			maxi.append(arr[i] + i)
		v1 = max(mini) - min(mini)
		v2 = max(maxi) - min(maxi)
		return max(v1, v2)


class Solution:

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


class Solution:

	def maxValue(self, arr, N):
		max1 = arr[0]
		min1 = arr[0]
		max2 = arr[0]
		min2 = arr[0]
		for i in range(1, N):
			if arr[i] - i > max1:
				max1 = arr[i] - i
			if arr[i] - i < min1:
				min1 = arr[i] - i
			if arr[i] + i > max2:
				max2 = arr[i] + i
			if arr[i] + i < min2:
				min2 = arr[i] + i
		if max1 - min1 > max2 - min2:
			return max1 - min1
		else:
			return max2 - min2


class Solution:

	def maxValue(self, a, N):
		max1 = a[0]
		min1 = a[0]
		ans = 0
		for i in range(N):
			ans = max(ans, i + a[i] - min1, i - a[i] + max1)
			min1 = min(min1, a[i] + i)
			max1 = max(max1, a[i] - i)
		return ans


class Solution:

	def maxValue(self, arr, N):
		mi = arr[0]
		ma = arr[0]
		ans = 0
		for i in range(1, N):
			ans = max(ans, i + arr[i] - mi, i - arr[i] + ma)
			mi = min(mi, arr[i] + i)
			ma = max(ma, arr[i] - i)
		return ans


import sys

class Solution:

	def maxValue(self, arr, n):
		max1 = -sys.maxsize
		max2 = -sys.maxsize
		min1 = 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)
		return max(max1 - min1, max2 - min2)


class Solution:

	def maxValue(self, arr, N):
		(min_1, min_2) = (999999, 999999)
		(max_1, max_2) = (0, 0)
		for (i, elementI) in enumerate(arr):
			min_1 = min(min_1, elementI + i)
			min_2 = min(min_2, elementI - i)
			max_1 = max(max_1, elementI + i)
			max_2 = max(max_2, elementI - i)
		return max(max_1 - min_1, max_2 - min_2)


import math

class Solution:

	def maxValue(self, a, N):
		import math
		min1 = math.inf
		max1 = -math.inf
		min2 = math.inf
		max2 = -math.inf
		for i in range(N):
			max1 = max(max1, a[i] + i)
			min1 = min(min1, a[i] + i)
			min2 = min(min2, i - arr[i])
			max2 = max(max2, i - arr[i])
		return max(max1 - min1, max2 - min2)