在給定一個數組的數組

找到兩個元素從零最遠的總和，什麼是最時間和空間有效的算法來找到最遠的兩個元素，從零該數組中的總和？在給定一個數組的數組

編輯例如，[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

在給定一個數組的數組

回答

相關問題