最大二次元サブセット和

Question

整数の行列の最大二次元サブセットを計算するアルゴリズムを書くタスクが与えられました。 - しかし、私はそのようなアルゴリズムのための助けに興味がありません、私は可能性としてこれを解決する可能性のある最悪の場合の複雑さを知ることにもっと興味があります。

私たちの現在のアルゴリズムは、O（n^3）に似ています。

私は行列を複数の部分行列に分割することで、行列内の要素を単純に足し合わせることで、分けて征服することを検討してきました。近似解を見つけるために考慮しなければならない行列の数を制限する。

Answer 1

私はこれを行うより良い方法はないと考えました。 - 少なくとも、まだ人に知られていない。 そして、私は、そのシンプルな理由から、私が得た解決策に固執するつもりです。

Answer 2

最悪の場合（徹底的な検索）はO（n^3）よりもであることは間違いなくありません。これについてはWeb上でいくつかの説明があります。

ベストケースは、O（1）よりもはるかに優れています。すべての要素が負でない場合、答えは行列自体です。要素が正でない場合、その答えはその値がゼロに最も近い要素です。

同様に、行列の端に非正の整数以外の行/列全体がある場合は、検索でこれらを切り捨てることができます。