打印 x 的最大值，其中 x = |(A[i] – A[j]) + (i – j)|

Question

Directi面试中被问到的问题取一个输入数组，比如 A 并打印 x 的最大值，其中x = |(A[i] – A[j]) + (i – j)|Constraints:Max array size: 20000Time limit: 0.1s时间限制是这个问题的主要因素。这是设置者针对此问题的解决方案。'''THE BRUTE FORCE APPROACHdef maximum(arr):    res=0                n=len(arr)    for i in range (n):        for j in range(n):            res=max(res,abs(arr[i]-arr[j])+abs(i-j))    return res '''import sysdef maximum(arr):    max1=max2=-sys.maxsize-1    min1=min2=sys.maxsize    ans=0    n=len(arr)    for i in range(n):           max1=max(max1,arr[i]+i)        max2=max(max2,arr[i]-i)        min1=min(min1,arr[i]+i)        min2=min(min2,arr[i]-i)    ans=max(ans,max2-min2)        ans=max(ans,max1-min1)    return ans        但我尝试使用解决问题sortdef maximum(array):    n=len(array)    array.sort()    return (array[n-1]-array[0]) + (n-1)        if __name__=="__main__":    n=int(input())    array= list(map(int,input("\nEnter the numbers : ").strip().split()))[:n]    print(maximum(array))我的方法正确吗？优化了吗？提前致谢。

Answer 1

建议的首先排序和获取元素的答案是不正确的。以反例为例：[2,1,3]

• 此问题的解决方案应产生 3：(3-1) + (2-1)或 (3-2) + (2-0)

• 但是，建议的解决方案将产生 4：(3-1) + (2-0)

---

一个可能的（线性时间）解决方案：

让我们从一些代数开始，暂时去掉绝对值。

(A[i] – A[j]) + (i – j) = (A[i] + i) - (A[j] + j)

我们正在寻找最大价值，所以

• 我们想最小化的价值(A[j] + j)

• 我们想要最大化 的价值(A[i] + i)。

• 请注意，它们彼此完全独立。

您可以找到两个整数，一个使 最大化(A[i] + i)，另一个使 最小化(A[j] + j)。找到这样的 2 个数字可以简单地在线性传递中完成。

以相反的方式重复（当(A[i] – A[j]) + (i – j)为负时）：

• 找到最小化的 i(A[i] + i)

• 很好j，最大化(A[j] + j)。

两者都在线性时间内完成，产生O(n)解决方案

Answer 2

排序会扰乱原始数组，并且元素在各自索引处的映射会丢失。所以从逻辑上讲，排序会导致错误的答案。

例如，正如@amit 在他的评论中正确描述的那样：

A = [2, 1, 3]

正确答案 = 3

建议的解决方案答案 = 4