数组中的最大绝对差

我遇到了这个算法问题。我能够实现 O(n^2) 解决方案。有没有更好的方法在 O(n) 时间内做到这一点？

问题：

给你一个包含 N 个整数的数组，A1, A2 ,…, AN。返回最大值f(i, j)对全部1 ≤ i, j ≤ N. f(i, j)定义为|A[i] - A[j]| + |i - j|, where |x|表示x的绝对值。

Example:

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

所以，我们返回 5。

我的答案：

public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int maxSum = 0;

        for(int i=1; i<=A.size()-1; i++){
            for(int j=i+1; j<=A.size(); j++){
                int tempSum = sum(A.get(i-1), A.get(j-1), i, j);

                if(tempSum > maxSum) {
                    maxSum = tempSum;
                }
            }
        }

        return maxSum;
    }

    public int sum(int Ai, int Aj, int i, int j) {
        return Math.abs(Ai-Aj) + Math.abs(i-j);
    }
}

另外，在我的解决方案中，内部循环从 i + 1 运行到 N，因此该循环的最坏情况是 N-1。我的整体解决方案仍然是 O(n^2) 吗？

是的，你的解决方案仍然是O(N^2) as (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2.

我将展示如何在线性时间内解决更一般的问题：给出 2D 空间中的点列表 (x[i], y[i])，找到两个最远的点（相对于曼哈顿距离）。

1. 让我们找到以下点：max(x[i] + y[i])、max(-x[i] + y[i])、max(-y[i] + x[i]) 和 max(- x[i] - y[i]) 在所有 i 中。

2. 让我们计算列表中每个点与上一步中选择的四个点之间的距离，并选择最大的一个。该算法显然在线性时间内工作，因为它考虑了4 * N点对。我声称这是正确的。

3. 为什么？让我们固定一个点 (x[k], y[k]) 并尝试找到离它最远的点。考虑任意点 (x[i], y[i])。让我们扩大它们的坐标之间的差异的绝对值。我们假设它是x[i] + x[k] + y[i] + y[k] = (x[k] + y[k]) + x[i] + y[i]。第一项是常数。如果x[i] + y[i]不是所有中的最大值i, (x[i], y[i])不可能是最远的。其他三种情况（取决于展开式中 x[i] 和 y[i] 的符号）以相同的方式处理。