題目

給你兩個長度相等的整數陣列，返回下面表示式的最大值：

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中下標 i，j 滿足 0 <= i, j < arr1.length。

示例 1：輸入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6] 輸出：13

示例 2：輸入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4] 輸出：20

提示：2 <= arr1.length == arr2.length <= 40000

-10^6 <= arr1[i], arr2[i] <= 10^6

1、數學；時間複雜度O(n)，空間複雜度O(n)

func maxAbsValExpr(arr1 []int, arr2 []int) int {	/*		|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|		=  (arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)		=  (arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)		=  (arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)		=  (arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)		= -(arr1[i] + arr2[i] + i) + (arr1[j] + arr2[j] + j)		= -(arr1[i] + arr2[i] - i) + (arr1[j] + arr2[j] - j)		= -(arr1[i] - arr2[i] + i) + (arr1[j] - arr2[j] + j)		= -(arr1[i] - arr2[i] - i) + (arr1[j] - arr2[j] - j)		其中：		A = arr1[i] + arr2[i] + i		B = arr1[i] + arr2[i] - i		C = arr1[i] - arr2[i] + i		D = arr1[i] - arr2[i] - i		結果：		max( |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|)		= max(max(A) - min(A),max(B) - min(B),max(C) - min(C), max(D) - min(D))	*/	arr := make([][]int, 4)	for i := 0; i < len(arr1); i++ {		a, b := arr1[i], arr2[i]		arr[0] = append(arr[0], a+b+i)		arr[1] = append(arr[1], a+b-i)		arr[2] = append(arr[2], a-b+i)		arr[3] = append(arr[3], a-b-i)	}	a, b, c, d := getValue(arr[0]), getValue(arr[1]), getValue(arr[2]), getValue(arr[3])	return max(a, max(b, max(c, d)))}func max(a, b int) int {	if a > b {		return a	}	return b}func getValue(arr []int) int {	minValue, maxValue := arr[0], arr[0]	for i := 0; i < len(arr); i++ {		if arr[i] > maxValue {			maxValue = arr[i]		}		if arr[i] < minValue {			minValue = arr[i]		}	}	return maxValue - minValue}

2、數學；時間複雜度O(n)，空間複雜度O(1)

func maxAbsValExpr(arr1 []int, arr2 []int) int {	aMaxValue, bMaxValue, cMaxValue, dMaxValue := math.MinInt32, math.MinInt32, math.MinInt32, math.MinInt32	aMinValue, bMinValue, cMinValue, dMinValue := math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32	for i := 0; i < len(arr1); i++ {		aMaxValue = max(aMaxValue, arr1[i]+arr2[i]+i)		aMinValue = min(aMinValue, arr1[i]+arr2[i]+i)		bMaxValue = max(bMaxValue, arr1[i]+arr2[i]-i)		bMinValue = min(bMinValue, arr1[i]+arr2[i]-i)		cMaxValue = max(cMaxValue, arr1[i]-arr2[i]+i)		cMinValue = min(cMinValue, arr1[i]-arr2[i]+i)		dMaxValue = max(dMaxValue, arr1[i]-arr2[i]-i)		dMinValue = min(dMinValue, arr1[i]-arr2[i]-i)	}	a, b := aMaxValue-aMinValue, bMaxValue-bMinValue	c, d := cMaxValue-cMinValue, dMaxValue-dMinValue	return max(a, max(b, max(c, d)))}func max(a, b int) int {	if a > b {		return a	}	return b}func min(a, b int) int {	if a > b {		return b	}	return a}

Medium題目，暴力法會超時，分析一下把時間複雜度將為O(n)