N 個のゼロ以外のエントリを持つスパースな mxn 行列があります。
の修正版は、十分にスパースな行列の従来の Kadane のアルゴリズムを打ち負かすKadane's 2-d algorithm、時間内の最大和部分四角形を見つけることができます。
ここで、マトリックスの 1 つのエントリが変更された場合に、最適なソリューションをすばやく更新できるかどうかを知りたいと考えています。
「すぐに」とは、次のような意味です。
おそらく、行列がスパースでなくてもうまくいく可能性があります。O(m N log n)O(m^2 n)O(m log n) time or bettera solution, however a solution when N = O(min(m,n)) would be ok