题解 | 最大 FST 距离

import sys
n=int(input())
a=list(map(int,sys.stdin.readline().split()))
#将i^2看作xi，pi^2看作yi
#fst(i,j)=|xi-xj|+|yi-yj|
#FST距离的公式恰好是两个点(xi,yi)和(xj,yj)之间的曼哈顿距离（也称L1距离）

#可将其转换为切比雪夫距离（L∞距离）相关的问题。 对于任意两点(a,b)和(c,d)它们的曼哈顿距离为： 
#|a-c|+|b-d|=max(|(a+b)-(c+d)|,|(a-b)-(c-d)|)   
# 将这个恒等式应用到我们的问题中，fst(i,j)=max(|(xi+yi)-(xj+yj)|,|(xi-yi)-(xj-yj)|)
U = list()#存储xi+yi的值=i^2+pi^2 最后用Umax-Umin即可
V = list()#存储xi-yi的值=i^2-pi^2 最后求Vmax-Vmin

for i in range(n):
    #下标从0开始注意加1
    U.append((i+1)**2+a[i]**2)
    V.append((i+1)**2-a[i]**2)
U.sort()
V.sort()
print(max(abs(U[-1]-U[0]),abs(V[-1]-V[0])))