疎行列内の最大和小矩形

Question

NxN行列内の最大合計の部分矩形を見つけることは、他の柱で指摘されているように、2-dカダンのアルゴリズムを用いてO(n^3)時間で行うことができる。しかし、行列が疎である場合、具体的にはO(n)の非ゼロエントリの場合、O(n^3)の時間を叩くことができますか？

私が興味を持っている現在のアプリケーションでは、行列の各行と各列の非ゼロ値を最大でも1つと仮定することで十分です。しかし、私の将来のアプリケーションでは、この仮定は適切ではないかもしれません（まばらさだけが保持されます）。そして、とにかく私の数学的な直感は、単に希薄さを利用する良い解決法があり、行列が対角行列と置換行列の積である。

Answer 1

はい、これは良い結果が得られます。すべての

まずは、O(1)における配列の最大部分配列の合計を探すO(logn)時間

に

1. 更新根本的な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の右側で終わる最大サブアレイの和 'の左側で開始するm個のサブアレイ上記の定義に基づいて複数の範囲

は、我々が見出し得ます更新ルール以下：任意の内部ノードvとその子のために任意のリーフノードvについては

• 、S[v] = A[v]、M[v] = L[v] = R[v] = max{0, A[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番目とj番目の行に固定すると、問題は1Dの最大サブアレイの合計問題に変わります。ここで、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)より優れています。