打印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

建议的答案是，首先排序并获取元素，这是不正确的。举一个反例：[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)。查找这两个数字可以简单地在线性过程中完成

以另一种方式重复（当(A[i] – A[j]) + (i – j)为负时）：

• 找到使(A[i] + i)最小化的i
• 精细的j使(A[j] + j)最大化

两者都是在线性时间内完成的，产生O(n)解

Answer 2

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

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

A=[2,1,3]

正确答案=3

建议解决方案的答案=4