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

Question

️直接面试中提出的问题

取一个输入数组，比如A，然后打印x的最大值 其中x = |(A[i] – A[j]) + (i – j)|

Constraints:
Max array size: 20000
Time limit: 0.1s

时间限制是这个问题的一个主要因素

这是这个问题的设定者的解决方案

'''
THE BRUTE FORCE APPROACH
def 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 sys


def 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
        

但是我试着用sort解决这个问题

def 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

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

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

A=[2,1,3]

正确答案=3

建议解决方案的答案=4