「真」元素的最大連續方形子矩陣

這是一個採訪問題：給定一個布爾矩陣找到最大的連續方形子矩陣的大小，其中只包含「真實」元素。「真」元素的最大連續方形子矩陣

我在SO上發現了這個question，但沒有明白答案。所提出的算法將一條對角線從左上方移動到右下方，並隨着線條的進行跟蹤「真」元素的矩形。

我的問題：

如何跟蹤算法中的矩形的？
爲什麼我們移動對角線一行？如果我們移動一條垂直/水平線或兩者，會發生什麼？
如何計算算法的複雜性？

2012-07-29 Michael

重複：http://stackoverflow.com/questions/3806520/finding-maximum-size-sub-matrix-of-all-1s-in-a-matrix-having-1s-and-0s – Klark 2012-07-29 19:35:13

@SINTER謝謝。答案中最有趣的部分並不清楚。他們說有_square_子矩陣的O（N * N）的DP解決方案，但沒有詳細說明。我認爲這正是我期待的。 – Michael 2012-07-30 06:14:43

我不明白the answer in the link you posted，我不認爲在那裏給出的複雜性最適合您的問題。（它要求有一個O(N^(3/2)*logN)算法，其中N=n*n是在原始矩陣中的元素的數量。）

對於你的最大平方子矩陣問題，有一個DP算法，其複雜性是與數量線性元素：

讓原來矩陣是A[n][n]，我們正在努力尋找一個矩陣B[n][n]，其中B[i][j]表示最大的子方陣，其右下角的元素是A[i][j]的大小。所以

for (i = 0 ; i < n ; ++i) 
    for (j = 0 ; j < n ; ++j) 
    if (A[i][j] == 0) B[i][j] = 0; 
    else { 
     if (B[i-1][j] != B[i][j-1]) { 
     B[i][j] = min(B[i-1][j], B[i][j-1]) + 1 
     } else { 
     if (A[i-B[i-1][j]][j-B[i-1][j]] == 1) 
      B[i][j] = B[i-1][j] + 1; 
     else 
      B[i][j] = B[i-1][j]; 
     } 
    }

而最大的B [i] [j]就是答案。

p.s.我沒有檢查數組範圍的簡化。您可以考慮超出範圍的元素爲零。

來源

2012-07-30 08:59:32 RoBa

太棒了！非常感謝。看起來像我正在尋找的解決方案。 – Michael 2012-07-30 12:25:02

「真」元素的最大連續方形子矩陣

回答

相關問題