Leetcode 1131.绝对值最大值表达式问题

Question

给定两个长度相等的整数数组，返回的最大值为：

|arr1[i] - arr1[j]| + |arr2[i] - arr2[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

public class Solution {
public int MaxAbsValExpr(int[] arr1, int[] arr2) {
int max = 0;
for (int i =0; i < arr1.Length; i++){
for (int k =i+1; k < arr1.Length; k++){
if (Math.Abs(arr1[i] - arr1[k]) + Math.Abs(arr2[i] - arr2[k]) + Math.Abs(i - k) > max){
max = Math.Abs(arr1[i] - arr1[k]) + Math.Abs(arr2[i] - arr2[k]) + Math.Abs(i - k);
}
}
}
return max; 
}}

这通过了大多数测试用例；超过时间限制"；当测试用例的数组中有数百个六位数的值时。我试着在网上看看如何用c#缩短它，但我不知道还能做些什么让它更快。

Answer 1

您遇到了"超过时间限制"；，这是因为你的算法执行时间太长，而且计算机超时。正如@Flydog57所评论的，嵌套循环可能非常非常昂贵，应该避免。他还提出了一种在没有嵌套循环的情况下实现算法的方法。以下是PHP中的实现(我不知道C#(：

/**
* Find the indexes of the max and min values in $arr.
*
* @param array $arr
* @return array
*/
protected function minMaxIndexes(Array $arr)
{
// Initialize variables indexes and values by the 1st element of $arr.
[$i0, $v0, $i1, $v1] = [0, $arr[0], 0, $arr[0]];
for ($i = 1, $size = count($arr); $i < $size; ++$i) {
if ($v0 > $arr[$i]) {
$v0 = $arr[$i];
$i0 = $i;
} elseif ($v1 < $arr[$i]) {
$v1 = $arr[$i];
$i1 = $i;
}
}
return [$i0, $i1];
}
public function maxAbsValExpr(Array $arr1, Array $arr2)
{
[$i, $j] = $this->minMaxIndexes($arr1);
$max1 = abs($arr1[$i] - $arr1[$j]) + abs($arr2[$i] - $arr2[$j]) + abs($i - $j);
[$i, $j] = $this->minMaxIndexes($arr2);
$max2 = abs($arr1[$i] - $arr1[$j]) + abs($arr2[$i] - $arr2[$j]) + abs($i - $j);
return max($max1, $max2);
}

正如你所看到的，for循环是N-1的2倍，如果我的计算正确的话，它比N(N-1)的嵌套循环快N/2倍。也就是说，对于1密耳的阵列长度，它的速度是500k倍。