在给定一个数组的数组

找到两个元素从零最远的总和，什么是最时间和空间有效的算法来找到最远的两个元素，从零该数组中的总和？在给定一个数组的数组

编辑例如，[1，-1，3，6，-10]具有最远的总和等于-11等于（-1）+（ - 10）。

2011-12-15 Qiang Li

你有什么确切的最远总和是什么意思？ ...如果可能的话提供一些例子。 – 2011-12-15 07:32:54

请更准确地回答你的问题。一个简单的公式可以帮助消除歧义，并显示您正在寻找什么，例如max_ {i，j} | x_i + x_j |。 – thiton 2011-12-15 09:06:56

@RaviGupta，请参阅我的编辑。 – 2011-12-15 19:15:27

使用赛比较方法来找到最大的和第二大的元件使用比较最少，在总n+log(n)-2。这样做两次，第一次找到最大和第二大要素，说Z和Y，重新寻找最小和第二小的元素，说A和B。那么答案是Z+Y或-A-B，所以再有一个比较可以解决这个问题。总的来说，这需要2n+2log(n)-3比较。这仍然是O(n)，但实际上比扫描整个列表4次要快，找到A,B,Y,Z（总共使用4n-5比较）。

的比赛方法，很好地与这两个教程图片和示例代码解释：one和two

来源

2011-12-15 16:27:42 PengOne

只是遍历数组，记录到目前为止遇到的最小和最大元素。这是时间O(n)，空间O(1)，显然你做不到比这更好。

int GetAnswer(int[] arr){ 
    int min = arr[0]; 
    int max = arr[0]; 
    int maxDistSum = 0; 

    for (int i = 1; i < arr.Length; ++i) 
    { 
     int x = arr[i]; 
     if(Math.Abs(maxDistSum) < Math.Abs(max+x)) maxDistSum = max+x; 
     if(Math.Abs(maxDistSum) < Math.Abs(min+x)) maxDistSum = min+x; 

     if(x < min) min = x; 
     if(x > max) max = x; 
    } 

    return maxDistSum; 
}

关键的观察是，最远的距离是两个最小的元素的总和或两个最大的总和。

来源

2011-12-15 07:17:11

让我们看看这个问题，从一般的角度来看：

找到k整数数组中的最大的一笔。

从跟踪FIRST k个整数开始 - 保持它们按顺序排序。
迭代整个数组，测试每个整数到目前为止保存的整数的最小值。
- 如果它大于已保存整数的最小值，请将其替换为最小值，然后将其鼓泡至适当的排序位置。

当你完成数组，你有你的最大ķ整数。现在

您可以轻松地将此应用到k=2。

来源

2011-12-15 07:23:45 corsiKa

如果您指的是其绝对值最大的总和，它可以是最大总和或最小总和。最大的总和是两个最大元素的总和。最小的总和是两个最小元素的总和。

所以你需要找到四个值：最大值，第二最大值，最小值，第二最小值。您可以在O（n）时间和O（1）内存中一次完成。我怀疑这个问题可能是关于最小化O（n）中的常量 - 您可以通过以五个元素进行元素排序，每五个元素进行排序（可以在7个比较中完成），并将两个顶层元素与当前最大元素进行比较（最差的情况下是3次比较），以及带有当前最小元素的两个底部元素（同上）。这给出了每个元素的2.6个比较，这是明显算法的每个元素的3次比较的小改进。

然后，只需总结两个最大元素，总结两个分钟元件和采取取其值具有较大的绝对值（）。

来源

2011-12-15 15:58:13

在给定一个数组的数组

回答

相关问题