题解 | #最大 FST 距离#

根据FST的定义，知其等价于求“曼哈顿距离最值”。
套用公式：

\begin{align} \text{设 P 和 Q如下} \\ P &= x + y = (i+1)^2 + a[i]^2 \\ Q &= x - y = (i+1)^2 - a[i]^2 \\ RET &= max(max(x+y)-min(x+y), max(x-y)-min(x-y)) \\ &=max(max(P) - min(P), max(Q) - min(Q)) \\ \end{align}

一次遍历求出maxP、minP、maxQ、minQ，最后求最值即可。具体代码如下：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = in.nextInt();
        }
        System.out.println(maxFst(data));
    }

    public static long maxFst(int[] data) {
        // dist(𝑖,𝑗)=∣𝑖^2−𝑗^2∣+∣𝐴𝑖^2−𝐴𝑗^2∣
        // P = i^2 + Ai^2    Q = i^2 - Ai^2
        // Ret = max (
        //  max(P) - min(P),
        //  max(Q) - min(Q) )
        long maxP = Long.MIN_VALUE;
        long minP = Long.MAX_VALUE;
        long maxQ = Long.MIN_VALUE;
        long minQ = Long.MAX_VALUE;
        long p, q;
        for (int i = 1; i <= data.length; i++) {
            p = (long) i * i + (long) data[i - 1] * data[i - 1];
            q = (long) i * i - (long) data[i - 1] * data[i - 1];
            maxP = Math.max(maxP, p);
            minP = Math.min(minP, p);
            maxQ = Math.max(maxQ, q);
            minQ = Math.min(minQ, q);
        }
        return Math.max(maxP - minP, maxQ - minQ);
    }
}