Leetcode: 【每日一题】- 2020-01-06 - 1131. 绝对值表达式的最大值

[azl397985856]

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

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

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

 

示例 1：

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

输入：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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-of-absolute-value-expression
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[unclegem]

|A| + |B| = max(A+B, A-B, -A+B, -A-B)给他推广到三个绝对值就是从八个最大值中取值，接下来把所谓的A，B啥的都带入式子里，然后同一个下标的放到一起，你会发现比如A-B和B-A其实是一样的，无非多了个负号，因为下标i和下标j的式子是一样的并且还是相减，就可以把两个变成了一个（相当于用最大的减去最小的），最后把八个变成了四个求最大值即可。

    public int maxAbsValExpr(int[] arr1, int[] arr2) {

        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        int max4 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        int min3 = Integer.MAX_VALUE;
        int min4 = Integer.MAX_VALUE;

        for (int i = 0; i < arr1.length; i++) {

            max1 = Math.max(max1, arr1[i] + arr2[i] + i);
            min1 = Math.min(min1, arr1[i] + arr2[i] + i);
            max2 = Math.max(max2, arr1[i] + arr2[i] - i);
            min2 = Math.min(min2, arr1[i] + arr2[i] - i);
            max3 = Math.max(max3, arr1[i] - arr2[i] + i);
            min3 = Math.min(min3, arr1[i] - arr2[i] + i);
            max4 = Math.max(max4, arr1[i] - arr2[i] - i);
            min4 = Math.min(min4, arr1[i] - arr2[i] - i);

        }
        return Math.max(Math.max(max1 - min1, max2 - min2), 
                        Math.max(max3 - min3, max4 - min4));
    }

[azl397985856]

@unclegem tql

[unclegem]

@unclegem tql

菜得很:P

[azl397985856]

@unclegem 有一点，你的解释说可以用四个，但是代码还是八个。

[unclegem]

@unclegem 有一点，你的解释说可以用四个，但是代码还是八个。

是4个啦，因为8个式子约减后每个都是最大值-最小值，我这里只用了4个Max值和Min值，就是4个式子。

拿8个式子其中两个举例：
(arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j) 和 (arr1[j] + arr2[j] + j) - (arr1[i] + arr2[i] + i)
这俩合到一起就是max(arr1[x] + arr2[x] + x) - min(arr1[x] + arr2[x] + x)

[azl397985856]

@unclegem 抱歉 抱歉 看错了

[azl397985856]

参考答案： https://github.com/azl397985856/leetcode/blob/master/problems/1131.maximum-of-absolute-value-expression.md

[mst123]

认领

[azl397985856]

@mst123 ok 期待你的 pr