稀疏矩陣中的最大總和子矩形

Question

如在其他帖子中指出的那樣，使用2-k kadane算法可以在O(n^3)時間內完成在NxN矩陣中找到最大總和子矩形。但是，如果矩陣稀疏，特別是O(n)非零條目，那麼是否可以打時間？

如果有幫助，對於我感興趣的當前應用程序，只需在每行和矩陣的每一列中都有一個假設至多有一個非零值的解決方案就足夠了。然而，在我未來的應用中，這種假設可能不合適（只是稀疏性會持續），而且無論如何，我的數學直覺是，可能有很好的解決方案只是利用稀疏性，不會進一步利用矩陣對角線和置換矩陣的乘積。

Answer 1

是的，它可以做得更好。

首先，讓我們想想的數據結構，使我們能夠

1. 更新底層的一維數組的任何單值O(logn)時間
2. 查找O(1)陣列的最大子數組的總和時間

實際上，看起來像下面的平衡二叉樹可以完成這項工作。樹形結構可以描述爲：

1. 樹的每個葉節點代表數組的每個元素。
2. 如果內部節點覆蓋範圍[a, b]，則其左側子區域覆蓋範圍[a, c]及其右側子區域覆蓋範圍[c + 1, b]，其中c = floor((a + b)/2))。

3. 根節點覆蓋範圍[1, n]。

        O 
           / \ 
          /  \ 
          /   \ 
         /    \ 
         /     \ 
         O      O 
        / \     / \ 
       / \    / \ 
       /  \    /  \ 
       O   O   O   O 
   /\  /\  /\  /\ 
   o  o  o  o  o  o  o  o 
   A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 
   

有附連到每個節點v 4個字段（包括葉節點和內部節點）：

• S[v]：所有值在v的範圍的總和
• M[v] ：v的範圍內的最大子陣列總和
• L[v]：最大值開始於v左側米子陣列：■範圍

基於上述定義的範圍

R[v]，在v的右側端部的最大子陣列的總和'，我們可以找到以下更新規則：

• 對於任何葉節點v，S[v] = A[v]，M[v] = L[v] = R[v] = max{0, A[v]}
• 對於任何內部節點v及其子l和r，
  
  • S[v] = S[l] + S[r]
  • M[v] = max{M[l], M[r], R[l] + L[r]}
  • L[v] = max{L[l], L[r] + S[l]}
  • R[v] = max{R[r], R[l] + S[r]}

最後，我們可以實現在開始提到的操作。

• 要更新A[i]，我們可能會發現在樹中的相應葉節點，並更新沿其路徑到根使用上述規則的字段。
• 最大的子陣列和只是M[root]。

現在我們來討論如何使用這個數據結構來找到最大的矩形。如果我們將矩形的上一行和下一行固定爲i th和j th行，問題就變成了一維最大子陣列總和問題，其中A[k] = sum{B[i..j, k]}。關鍵的見解是，對於固定的i，如果我們按升序列舉j，我們可以使用上面的數據結構來維護底層的1D數組並快速找到答案。僞代碼描述了主意：

result = 0 
for i in (1, 2, ..., n) 
    set all fields of the binary tree T to 0 
    for j in (i, i + 1, ..., n) 
     for any k where B[j, k] != 0 
      T.update(k, A[k] + B[j, k]) 
     result = max{M[root], result} 
return result 

假設矩陣包含m非零元素，該算法的時間複雜度爲O(mn logn)。在你的情況m = O(n)，所以時間複雜度是O(n^2 logn)，並且比O(n^3)好。