（Python）题解 | 最大 FST 距离

from math import inf
import sys

def main():
    # 读取输入
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))

    # 处理特殊情况：n=1时没有合法的(i,j)对
    if n == 1:
        print(0)
        return

    # 分析问题：
    # 我们需要计算所有i<j时的表达式：j^2 - i^2 + |arr[i-1]^2 - arr[j-1]^2|
    # 这个表达式可以分为两种情况：
    # 情况1：当arr[j-1]^2 >= arr[i-1]^2时：
    #   j^2 - i^2 + arr[j-1]^2 - arr[i-1]^2 = (j^2 + arr[j-1]^2) - (i^2 + arr[i-1]^2)
    # 情况2：当arr[j-1]^2 < arr[i-1]^2时：
    #   j^2 - i^2 + arr[i-1]^2 - arr[j-1]^2 = (j^2 - arr[j-1]^2) - (i^2 - arr[i-1]^2)
    # 因此，我们需要分别计算这两种情况的最大值

    # 初始化变量：
    # max_diff_A记录情况1的最大值
    # min_A记录情况1的最小前缀值
    # max_diff_B记录情况2的最大值
    # min_B记录情况2的最小前缀值
    max_diff_A = -inf
    min_A = 1**2 + arr[0]**2  # i=1时的A值

    max_diff_B = -inf
    min_B = 1**2 - arr[0]**2  # i=1时的B值

    # 从i=2开始遍历（因为j>i，所以i最小是1，j最小是2）
    for j in range(2, n + 1):
        # 计算当前j的A值和B值
        curr_A = j**2 + arr[j-1]**2
        curr_B = j**2 - arr[j-1]**2

        # 更新情况1的最大差值
        max_diff_A = max(max_diff_A, curr_A - min_A)
        # 更新情况1的最小前缀值
        min_A = min(min_A, curr_A)

        # 更新情况2的最大差值
        max_diff_B = max(max_diff_B, curr_B - min_B)
        # 更新情况2的最小前缀值
        min_B = min(min_B, curr_B)

    # 最终结果是两种情况的最大值
    print(max(max_diff_A, max_diff_B))

if __name__ == "__main__":
    main()