InterviewBit – Maximum Absolute Difference

Source: Maximum Absolute Difference

You are given an array of N integers, A₁, A₂ ,…, A_N. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.
f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

For example,

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

So, we return 5.

---

解題：

1. 將示例先做成表格找出規律性；

0	3	4
3	0	5
4	5	0

2. 依照從示例看出之規律，基本上只需要計算表格上半部或下半部即可，無需將所有資料均執行運算：

           for i in range(0, N-1):

for j in range(i+1, N):

3. 還有更快速，只需要一個迴圈就可以解決的方法嗎？

取絕對值並使用同樣的陣列做運算，表示A[i] 跟 i 如不用絕對值公式abs()則分別各有正負共四種組合。使用第一個迴圈確認各自組合之最大值為何，再用第二個迴圈計算各組合之最大值與迴圈當下取到的A[i]及i四種組合運算是否可得出最大值。需注意第一個迴圈所算出之最大值在第二個迴圈內必須將運算正負號相反，這樣才能得出|A[i] – A[i]| + |i – i| = 0的正確結果。

code:

def maxArr(self, A):
    if not A: return 0
    N = len(A)
    mx1, mx2, mx3, mx4 = [-10**15] * 4
    for i in range(N):
        mx1 = max(mx1, A[i] + i)
        mx2 = max(mx2, - A[i] + i)
        mx3 = max(mx3, A[i] - i)
        mx4 = max(mx4, -A[i] - i)
    ans = -10**15
    for i in range(N):
        ans = max(ans, mx1 - A[i] - i);
        ans = max(ans, mx2 + A[i] - i);
        ans = max(ans, mx3 - A[i] + i);
        ans = max(ans, mx4 + A[i] + i);
    return ans

說實在這題我在沒看提示的狀況下完全想不到可以把abs拿掉並用正負號變換來做組合並把迴圈從兩個巢狀迴圈降為線性迴圈執行兩次即可。儘管這程式碼看起來很簡單，但內含的智慧跟創意也是很值得細細品味啊。

GitHub: GitHub – Maximum Absolute Difference