MxN マトリックスを指定すると、最大の合計数を持つ (連続した) サブマトリックスを見つけるプログラムを Java で作成しようとしています。次に、プログラムは部分行列の左上隅の座標と右下隅の座標を返す必要があります。行列には負の数を含めることができ、行列と部分行列の両方が正方形である必要はありません。
これがここで議論されているのを見ました:最大合計で部分行列を取得しますか? そして解決策はO（n ^ 3）のようです。私の友人は、かつてこの問題を O(n^2) で解くことができたと言っていました。ここでも提案。それは可能ですか？
この問題を最も効率的に解決できるコードはありますか?