尋找具有最大的一筆

Question

可能重複的子矩陣：
Finding a submatrix with the maximum possible sum in O(n^2)

我有一個N×N的矩陣。我想找出上述矩陣中具有最大元素總和的MxM子矩陣。

這是什麼效率算法。

Answer 1

我有一個在固定時間內擴大M和二次時候擴大N.當

第一子矩陣計算照常運行算法。保存總和。然後向右移動一行字段 - 兩個MxM矩陣重疊，因此您可以對兩個非重疊列進行求和。保存所有款項。現在您可以選擇該行的最大總和。

移到下一行。記得保存的總和？第一行和第二行的MxM矩陣再次重疊，因此您可以對MxM矩陣的第一行和最後一行進行求和並計算第二行的第一個和。

現在移到第二行的第二個和。做與上面相同的事情，但是你發現第一行的最後一行和第二行的第二個和重疊。

我知道這是有點令人困惑，如果你沒有得到它，讓我知道我會畫一些它的照片。該算法基於this answer中的論文。

編輯：我知道我答應的畫面，但這應該已經足夠了：

 
A AB AB AB AB B 
AC ABCD ABCD ABCD ABCD BD 
AC ABCD ABCD ABCD ABCD BD 
AC ABCD ABCD ABCD ABCD BD 
AC ABCD ABCD ABCD ABCD BD 
C CD CD CD CD D 

這四個submatices，A，B，C，d，定位是這樣的：

AB 
CD 

第一你計算A子矩陣的總和：sum（A）。這裏沒有優化。現在你要計算B：sum（B）的和。你可以像A一樣做，但注意A和B重疊。因此，您將和（A）分配到總和（B），計算垂直向量A AC AC AC AC的總和，如果從總和（B）減去，則計算垂直向量的總和B BD BD BD BD並將其加到總和（B）中。

 
sum(B) = sum(A) - sum(A AC AC AC AC) + sum(B BD BD BD BD) 

您有和（B）。現在您可以繼續並計算整個第一行子類。

移到第二行：matices C和D.您不必總和整個matice C，因爲在前一行中，您保存了sum（A）。注意他們再次重疊。您只需添加A和C之間的差異：

//code (1) 
subC = sum([A AB AB AB AB]) //as substract C 
addC = sum([C CD CD CD CD]) //as add C 
sum(C) = sum(A) - subC + addC 

您有總和（C）。現在你可以得到這樣的總和（D）：

//code (2) 
subD = sum([AB AB AB AB B]) //as substract D 
addD = sum([CD CD CD CD D]) //as add D 
sum(D) = sum(B) - subD + addD 

但比較subD與subC和addD vs addC。它們重疊！所以你可以這樣做：

你可以看到，而不是一個子矩陣的總和爲25，我們做6。對於MxM的每一個可能的大小，我們都有第一個子矩陣的MxM aditions，第一行和第一列的M * 2 + 2 aditions以及其餘的6個adition。