题目描述

给你两个长度相等的整数数组，返回下面表达式的最大值：

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中下标 i，j 满足 0 <= i, j < arr1.length。

样例

输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
输出：13

输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
输出：20

限制

• 2 <= arr1.length == arr2.length <= 40000
• -10^6 <= arr1[i], arr2[i] <= 10^6

算法

(暴力枚举) $O(n)$

1. 如果 i == j，则结果为 0，所以我们不妨假设 j < i（如果一个最优答案满足 i < j，则我们可以交换 i 和 j）。
2. 去掉绝对值符号，合并关于 i 的项和关于 j 的项后，有四种情况：
   • (arr1[i] + arr2[i] + i) - (arr1[j] + arr1[j] + j)
   • (- arr1[i] + arr2[i] + i) - (- arr1[j] + arr1[j] + j)
   • (arr1[i] - arr2[i] + i) - (arr1[j] - arr1[j] + j)
   • (- arr1[i] - arr2[i] + i) - (- arr1[j] - arr1[j] + j)
3. 分别处理这四种情况，假设第一个括号内为 A，第二个括号内为 B，则我们可以在线性的时间内求出 A - B 的最大值。（枚举 i 的过程中求 A - B，然后更新 B最小值。）
4. 四种情况的最大值就是答案。且我们求出的最大值一定是符合规则的，即符合绝对值的求值规则。否则，假设我们找到的答案 i 和 j 属于第一种情况，其中破坏了绝对值求值规则，即 arr[i] < arr1[j]，则我们可以通过第二种情况得到一个更优的答案，与当前答案是最好的矛盾。对于其他的情况也可以得到类似的矛盾，所以分别处理四种情况得到的最大值一定是最终绝对值表达式的最大值。

时间复杂度

• 线性遍历数组 4 次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int solve(int p1, int p2,
              const vector<int>& arr1, const vector<int>& arr2) {

        int n = arr1.size();
        int m = p1 * arr1[0] + p2 * arr2[0];

        int ans = 0;
        for (int i = 1; i < n; i++) {
            int t = p1 * arr1[i] + p2 * arr2[i] + i;
            ans = max(ans, t - m);
            m = min(m, t);
        }

        return ans;
    }

    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        return max(
                max(solve(1, 1, arr1, arr2), solve(-1, 1, arr1, arr2)),
                max(solve(1, -1, arr1, arr2), solve(-1, -1, arr1, arr2))
            );
    }
};