查找沒有重複元素的最大矩形

Question

查找唯一矩形（即，在給定子矩陣內不重複）的矩形連續子矩陣的最大尺寸。

我該如何解決這個問題？

Answer 1

您應該設置最大值爲0.迭代矩陣的行，如果它們不重複（無論如何），請將其大小與最大值進行比較。如果它更大，則存儲新的最大值並將其用於進一步迭代。如果您發現了新的最大值，請存儲您需要存儲的任何內容。因此，該算法是這樣的：

maximum <- 0 
for all rows as row 
    if (row is not repeating) then 
     if (row rectangle size > maximum) then 
      maximum <- new maximum 
      store whatever you need to store 
     end if 
    end if 
end for 

請注意，如果您還沒有進一步的信息，那麼它是沒有意義做一個二進制搜索，因爲你必須檢查每個矩形的大小。如果您對矩形有更多的瞭解，那麼算法可能會得到優化。

Answer 2

第一個想法（遞歸）：也許在整個數組中標識對，這將識別尊重約束。如果在位置x0，y0和x1，y1上有一個值v那麼你不能有一個包含這些位置的矩形，所以這將允許你從這些值構造一些可能的矩形並遞歸它們？另一個（動態編程）：從基本數組（大小爲1x1）開始，並嘗試將它們合併爲約束條件？